My first contribution to this lovely group of PDA-obsessed compatriots...
http://www.ranpura.com/resourceHome.html
I wrote a little perl script to reformat Mapquest's atlas pages (
http://www.mapquest.com/atlas/main.adp?region=world) in order to minimize extraneous content for PDAs. You can use any web converter with a link depth of 1 to download the whole atlas (I use iSiloX).
Note that there are over 300 maps in this atlas -- without image compression I think this would require around 70 Mb of space. iSiloX allows me to compress all images down to 25% of their original size, giving me an atlas that weighs in around 10 Mb.
If anyone knows of a better world atlas solution, please do get in touch. Mapquest is the only place I know to get decent looking maps (I have a T3 and no, line drawings aren't good enough!).