But I'm honestly questioning whether or not he should be able to take out 30% of a tower's health with one Q, which is on a 3-5 second (estimating) cooldown at max rank.
I'm ok with it.
As a tanky DPS champion, Nasus isn't like marksman, assassins, or mages where he builds DPS and gets some defensive mechanic for free (range and mobility for those).
Nasus gets damage for free so he can build his defensive mechanic.
And while other tanky DPS champions get decent AA steroids, Nasus's AD steroid is tied specifically to damaging other champions with his ult, and his armor/mr shred doesn't even effect towers. His only damage vs. towers is his Q, which doesn't do much of anything without stacks.
Consider what other tanky DPS champions have:
Mundo's 100~200 AD boost doesn't suck, Elises 120% AS steroid with spiderlings is pretty solid, Olaf's 80 AD and 80% AS. Even the CC tanks/supports in Taric, Alistar, Blitzcrank, and Rammus can output some decent tower damage with their steroids - Rammus with actual abilities on top of it.
Anyways - it's important to keep in mind with Nasus that his Q is the only damage he has against towers. He can't really build much in the way of offense, and if you leave a champion like Riven, Fiora, Vayne, Jinx, Kayle, Teemo, Heimerdinger, etc. alone with a tower - they can usually take it as fast as Nasus.