There are several people on this forum using N810s with 8GB microSD(HC) cards (with micro-mini adapter) with great results. The adapters can be a problem, but I'd suggest you do a search to find out the specifics.

SanDisk has announced 12GB and 16GB microSD(HC) cards are coming in the next few months, so storage shouldn't be a huge issue on either N800 or N810. And don't forget about that other storage device, "the internet".

Best thing for both devices is that to add storage, you just add another card. SD/mini/micro cards are all tiny, so it's easy to carry more than one.