I have an i-Blue 737 which I use with my N95 - I got hooked on the idea of GPS but frustrated with the **bleep**piness of the built-in unit.
Originally I got a GlobalSat BT-359 (a slimmed down version of the popular BT-338) which didn't work with the N95, often dropping the bluetooth connection, so I had to send it back.
However the i-Blue has worked very well, getting fast, reliable fixes and with a great battery life (it also has a low-power standby mode when the bluetooth isn't connected). The battery is swappable and it takes a standard Nokia BL-5C so I immediate had a spare from my old 6230i.
It's fairly small and light, about half the size and weight of the N95 - I just keep it in the outer pocket of my backpack. I had it recommended to me from someone on this forum who was using it with an N80 so should be compatible with that also.
Regarding the built-in GPS on the N95, plenty has been written about it, but basically it's not too good. The addition of "assisted GPS" means it locks on a bit quicker now, but using that feature potentially incurs network data charges, and probably won't work outside your home network.
Also it doesn't help with the general accuracy, which is poor, and it has a tendancy to lose the lock entirely when you close the case. I use it with Nokia Sports Tracker on bike rides, and the i-Blue is far better and doesn't flatten the battery like the built-in GPS does.
Even at the best of times, the built-in GPS jumps around a lot, which makes voice navigation (which I paid for the upgrade) go horribly wrong, telling you to double-back and turn left when you should be turning right, etc.