I love Terrain Navigator and use it quite a bit in my work. I haven't upgraded in a while and my version is a fussy printer. It doesn't remember settings very well but it would allow you to print out exactly the maps you need at any effective scale.

I have used it for generating everything from wall sized maps to quick pocket maps for navigating. I have also installed it on a netbook with a GPS for off road navigation. However, for printed versions to be usable and cover the entire state, it would be very bulky.

I agree that the Delorme Gazetteters might be your best solution if you need non-digital and the entire state. After that, I would suggest the USGS 1:100,000 maps. I think you can order them rolled as (opposed to folded) and possible stash the maps you need in one tube. Though the cost will add up.