For regional / world maps on the fly, I use Greenfish Map Generator. It's a great little program that throws out useable maps in a matter of seconds. I'd have to google it to get a link, and you can do that just as easily as me.

For quick random cities on the fly, I use the Random City Generator discussed here:

http://www.cartographersguild.com/showthread.php?t=4238

I don't know of a random dungeon generator, but there probably is one out there. However, for a quick tile dungeonmaker, I use Dungeonforge (again, simply google it). It's essentially a free (and less photorealistic) Dundjinni. Depends how much detail you want, and how much cash you have.

In the last few months, a guy called Sowellblack made something called Hexographer (it's on the Software thread here somewhere) I haven't got around to testing it yet <slaps own wrist> but you might find that useful. I gather it's an online hexmap generator.
If it were downloadable I might have played with it by now...

If you have an idea of the style of maps you want to produce, show us some pics or links and it may help us to suggest the right software.

Hope that helps.

PS all the above are free.