Thanks for ALL of the replies. It's more than I expected and has been extremely helpful. I didn't mean to abandon the thread for so long but work has taken up a lot of time this past week or so. Everything was read with interest, but I'll just pick out the following to reply to...
Don't listen to those people. Like, at all. I've been running a 5E campaign for two years, and I've literally never run an alleged "adventuring day". One encounter per day works fine. You have to understand what will challenge your PCs in those circumstances, of course, but that's true of any system. Dungeons? In my campaign there have been three. And that's a deliberate attempt by me to run more dungeons than I usually do. And range? Of course you should let your PCs come up with strategic ideas to control how encounters emerge.
The system is bare-bones not because these assumptions are baked into it, because (insofar as it's possible) they didn't want any assumptions baked into it. 5E is supposed to be the "do whatever you want with it" edition. Now, if you still feel like it's failed at that because of actual rules you don't like -- you mentioned Perception and AC? -- then by all means, give some of the other systems in this thread a look. Some of them are very good too. But for the love of all that is Good, don't be put off by self-proclaimed experts on the internet. They ruin everything.
You're right. I did allow myself to be put off somewhat by some posters here. Oddly it wasn't the people making criticisms of the 5e system that started me looking at other options, it was those who kept attacking such criticism with "you're playing it wrong" style responses. But nonethelss, you're right it's worth evaluating more myself. That said, whilst I'm out of time to replace it for this week's game and we'll be continuing with 5e a little longer, I am starting to find it not quite to my taste. I like much of it but it's also something of a two steps forward one step back affair for me. Again, a personal opinion based on my own preferences. Having followed up on some of the suggestions here, I actually am finding things out there I think I might enjoy running more. I don't think 5e is awful or anything - please don't think I do. But there's a lot of good stuff out there too.
Not edition warring here, but I'm just not thinking of 4e as a good fit when I read the OP. Am I missing something?
Not really. I mean 4e is so right in some ways, but so problematic in others. I'm sure I'm far from unique in that. I did actually look at running 4e when it came out and from a balance perspective it was sublime. I also found the built in background - points of light, the way they did the gods, the planar structure... wonderful. But at the time a number of things were show-stoppers for me. It seemed unplayable without a grid (ironically I'm now using a grid), it seemed to focus everything on combat and had the barest bones for non-combat and worst was the way mechanics seemed to divorce entirely from in-game meaning. The halfling is a fighter? Well they'll have 20 strength and arm-wrestle the minotaur cleric to the ground. That old grey-bearded wizard is 15th level? Well then they'll be bouncing up and down the mountain side like a frisky goat because that's how level bonus works whilst the strapping young peasant man will be out of breath and tumbling to his death. And other things... 4e was always the edition that I wished I could run. It was so perfect in so many ways, but everything was sacrificed on the alter of sacred balance.
Sword of Spirit mentioned the Flight spell which is interesting because that's one of the things that really hammered home to me why I didn't feel I could run 4e. It was so clearly written to prevent a player finding anything special or clever to do with it, and basically a high-powered bounce ability. 4e was the closest I've ever come to running D&D until the last month where my group asked me to run a fantasy game for a change. I've mellowed on some of my objections to 4e from back then but I looked at it again recently and felt it wasn't the answer this time around.
Now I've had a chance to read more, you want to give Burning Wheel a serious look. It's made of awesome for the campaign you just described.
I've heard of this, never knew what it was. I've now read through the Wikipedia entry and their website. I'm going to pass this one by unless you tell me I'm wrong in my impressions; but it seemed a little simple and it also seemed very focused on co-operative story-telling and rolls where players determined how NPCs would behave, resources available, etc. That's pretty much the polar opposite of my GM'ing style. I am very much a GM who creates a world and then tries to distance themself from it and let it unfold as it naturally would. Burning Wheel seems to be one of those games where the dice create a story for you all together as friends. That's utterly not me. I hate players. Players are the enemy. My job as GM is to set up a world where by default they will die and their job as players is to frustrate me in my desires.

Do not let the fact that I run a lot of social, politicking and investigation elements in my game deceive anyone into thinking I want to share my world-creating power! Diplomacy is just combat without a grid!
You might check out Low Fantasy Gaming RPG. It's a more dangerous/gritty/low magic d20 variant. Pretty easy to increase the magic level if you wish. Formal Party Retreat and improvised chase rules mean you dont have to worry about "balanced encounters" so much, and it has unified refresh mechanics (not different classes refreshing at different rates).
Free PDF (in my sig), or print via Lulu.
Edit - it also addresses some of your other concerns - the "long rest" is 1d6 days, so you can wilderness adventure with only the occasional battle between days, and you wont get the whole party nova-ing, because they dont automatically get refreshed the next dawn.
This was interesting. I looked at it following your suggestion (and the other poster). It's charming, I liked the layout and presentation of the PDF and I especially liked subtle references to F. W. Morganstern's great work and Big Trouble in Little China. It seemed good but I don't think I could actually replace D&D with it because there are too many elements of D&D that it has (purposefully) stripped. Higher level play is gone along with higher level magic. Classes are pared down to the essentials and gone are paladins, warlocks, et al. Even something I could reskin as these things. So whilst I thought it was a fun little system, it didn't fit my needs.
My books are packed for a move, so I can only give general impressions. The way flight was reduced to hovering above the ground was one thing I didn't like. I was okay with teleportation circles, but the old plane shift to a random location on another plane is one of my favorite things in D&D. I don't remember the polymorph sorts of stuff working the same. The attack spells were usually fine, it's more of the upper level utility sorts of spells that didn't make it in that I always think of as D&D.
I actually thought 4e did a very good job of addressing this with its rituals system. As a GM I thought that looked pretty liberating - I could just make up a ritual, give it whatever timing or ingredients I felt like if I wanted to restrict use, and then apply whatever I wanted. An overland flight ritual? Sure, not a problem! 4e didn't seem to care much what abilities people had so long as they couldn't break the combat system.
SAVAGE WORLDS
Tons of genres and the game is very balanced.
I've heard of this one, never looked at it. Thanks for the recommendation, I'll have a look.
Anyway, after all the replies, which have been interesting, I should say that I've been following a recommendation from early on and looking into the Hero system. It's, well... quite something. People weren't kidding when they said there was a lot of front-loaded work. But they also weren't wrong when they said it plays pretty quickly and elegantly once you start play. Usually a system leans towards being simple and light or more complex and heavy. Hero is unique in my experience in that it's simple and heavy. That's not a criticism, it's a complement. I should explain what I mean. The core approach is very simple and very consistent. Learning it wont take more than an hour or so. It's elegant and thus fairly easy to learn and balance. But then so are systems like Doctor Who: Adventures in Time and Space. What it also has are copious listings of powers and circumstances based on upon that simple core and that's new.
Anyone who has read this far through my post will have picked up that I am a fantastically picky and perfectionist person. Of the recommendations, Hero seems to be the only one that will satisfy my obsessiveness. I'm still getting a feel for it and the work required to make a D&D clone out of it is not trivial. However, it has a number of elements that I'm finding much to my tastes. Endurance as a core mechanic pleases me - I like the notion of different characters being able to battle on through slowly depleting reserves of stamina. Hit locations could be more elegantly implemented but I do like the idea of a bit more grittiness to combat. It's certainly capable of managing high level magic and whilst some of it is fiddly, it's pretty capable. For example, one of the first things I did to try and get my head around the system was to create a magic item. In this case, a flaming long-sword that exhausts the wielder over time (costs endurance each round it's used) but burns the wielder's foes and dazzles those who try to attack her in hand to hand. Making ports of D&D monsters seems relatively easy. I'm currently toying with creating different classes as templates, e.g. warlock, paladin, fighter, etc. If I can find a little time to do this, I will probably post it somewhere as a D&D conversion for Heroes.
In any case, unless the perfect system falls into my lap unexpectedly, I'm going to try and see what I can come up with in Hero 6e whilst the campaign carries on a little longer with D&D 5e. Really appreaciate so many helpful replies!
K.