Best things I got for my N95, (apart from a big memory card):
1. Nokia GPS receiver - actually I got this as part of a N770 Navigation Kit - but it's a really good receiver. Think it's something like CDW-3W or similar name, (memory fade). It's quite small (about the size of a big pack of gum) with good battery life and SirfStarIII so it locks on quite quickly.
2. CoPilot - it suits me better than Nokia Maps - although (imho) the navigation option for the latter is actually quite good value for money.
3. Good crystal case - tried a "cheap" one from a moby shop and that cracked within a couple of hours. The replacement - from the local O2 shop - was 1/2 the price and is still going strong three months later (although it's good and scuffed).
Maybe one of these days I'll be allowed to upgrade to the latest firmware. I'm with 3 (stop laughing please!) and when I checked last week they were still pushing v12 as the latest one.
Good phone though, shame that 3's customer service is laughably awful..