I've just bought a Bluenext BN909GR, it has a Sirf star III chipset which is supposed to be pretty good (go for the 20 channel version of the chipset).

The other competitor atm (afaict anyway) is the MDK chipset with 51 channels (there's an earlier 32 channel chipset, but I've not seen any comparisons of it). This has lower power consumption and is almost as sensitive (1dB difference), but was more expensive when I was just looking.

In terms of software, try maemo-mapper.