Aside from Costa, then...
Reigate and Coulsdon South have Jaconelli's, which appears to be an independent group of a couple of shops which sort of open when they feel like it... but the coffee is generally nice enough, if you can get it! Pity about a customer's dog dragging that table on the line at Coulsdon South recently, but such is life.
Redhill has Puccino's, as do quite a few stations in the South-East, I find. Service at those usually seems to be quite friendly. There are also a few places in the town centre which aren't bad, including some independent cafés. The town centre, during daylight hours, is in no way entirely as depressing as some people make out, once you've used your battlefield tactics to get past the yoof outside McDonald's.
Tonbridge, Brighton Waiting Room and Guildford, as well as possibly some other places, have the Flying Coffee Bean mini-chain. I haven't used them, but they seem to have a good reputation.
Hassocks café hasn't been open when I've popped by, but is rumoured to be considered invaluable by local residents of a morning, especially if Balcombe has broken again, or something. Hopefully the overall caffeinated experience will be enhanced when they've finished rebuilding the subway, which can add a fair bit of noise and mud!
If I must use a chain anywhere, I'm afraid, OP, it is usually Caffe Nero (not least because they're on my good books due to the O2 Priority free coffee).
