Kinda hate to recommend pilfering another indie developer's good idea, but Eschalon's use of the cartography skill was brilliant.

I'll put in another vote for alchemy, too. I like searching the countryside for ingredients. While the Wiz8 system was a little out-of-balance (too profitable), a potions-for-profit structure is a nice reward for players that develop the skill.