Nokia 6110 Navigator. It's the perfect companion for the tablet because with HSDPA it offers the highest speed currently available in my country and acts as a bluetooth GPS-device (essential for the 770/N800, still nice to have for the N810 because of AGPS.)
It was cheap, too: € 17,- isn't too much (no new contract, but subsidised via loyalty bonus points plus 12month data plan for €5,-/month)

Firmware is full of annoying little bugs, though, and I don't see any activity on Nokia's side to get it fixed. Pity.