One interesting quest I've seen was in EQOA. It was a king of the hill type quest. You had to defend an NPC against hordes of MOBS. Granted, it was an escort mission of sorts. Granted also, it required 20 or so people to make sure all the mobs were put down. But it had a different objective than "kill x foozles".
It's also really difficult to make quests accessible by non combat methods without making them trivial. Stealth is alright, but most of the non-stealth missions in fallout turned into "If you have Int > 25, pick options 3, 2, 1, and 4 to complete the quest."