I believe the ideal combination with a N800 is a smartphone like a Treo. That way, you get your BT dialup covered, you can just carry the phone and still get online if you don't want to carry the N800, and you get the PDA functions the N800 is missing.

I use a Treo 650, but I think you can now get faster connectivity with a more recent model.