It's interesting. I have always been inclined towards long prep time, lots of encounter design and detail spent plotting out where the PCs might go, who they might interact with, etc. The few times I tried winging it in 3rd edition went poorly - grabbing monsters out of the books just ran into too many problems due to the occasionally poor balance of the CR system.
4E didn't really change that - prep became easier, but it was still my habit. Until a few weeks ago, when the party went on a completely different mission than I was prepared for... and I discovered it was very, very simple (at least for me) to just run things on the fly. I knew the basics of the plot, and for the encounters, I just grabbed the books, some appropriate (or reflavored) monsters, and went from there.
I can definitely understand how it might seem a harder challenge, if you expect to grab 5 or 6 monsters in a fight... but you don't always have to. Use of elites, solos, or simply grabbing a couple similar monsters and adjusting them a bit on the fly.
One of the encounters I ran like this - it was a group of Ice Devils sent to assassinate the party. 6 Ice Devils seemed rather boring, so I divided them into groups of three, had each pair seem slightly different (one group had oversized longspears, another were big and bulky, the last was quick and agile), and then slightly modified each group accordingly - choosing one key aspect of the Ice Devil and adjusting it for each group. The longspear guys got an extra square of reach and a small slide on their longspear attack. The bulky guys got a slightly larger breath weapon and cold aura. The agile guys got to swing twice with their claw attack.
The final result - 20 seconds of minor adjustments, and the enemies felt distinct on the field, and I was still able to run out of one page in the MM. I think coupling interesting abilities with good descriptions is the key, especially with decent set pieces. It doesn't require tons of planning to get decent terrain, either - even just a fight in an inn gives you windows to throw people through, tables to get tossed onto, stuff like that.
While I understand your point that overpowered elements in 3rd might have been more memorable (like unstoppable grapple checks), those memories aren't always good ones - whereas harpooning someone through a second-story window in an inn isn't going to end the combat for them, but should still be a memorable moment!
Anyway, I'm definitely not trying to discount your experience or dismiss your issues - mainly just give examples that I feel the same sort of moments can come up in 4E without having to spend hours prepping for them. Running entirely on the fly - or prepping some basic encounters and using reflavoring and good in-combat description to personalize them - could still be a viable option if you are willing to genuinely give it a try. Try slightly more condensed fights - an elite leader, a couple similar henchman (though they can be distinct in appearance even if mechanically similar or the same), and you shouldn't be overwhelmed with too many monsters to keep track of. Add in the occasional fully-statted encounter for a key moment, and you have a decent approach without too much advance prepwork.
Part of what I'm saying here is that, as careful as the numbers may look in 4E... you really can get away with quite a bit of fiddling with things on the fly. You don't need to redesign the centaur from the ground up to run it as an ally - maybe level off hp to be close to the group, and avoid use of any attacks that are too powerful (mass stuns, etc.) The companion rules are great for designing a long-term party member, sure - but just running a slightly modded monsters is still functional, in the end.
In the end, I think the key is to worry less about the mechanics and focus first on what is going on. Skill challenges shouldn't be driven by one specific solution to a problem - instead, see where the party takes it. Throw some DCs at them, let the challenge evolve from there based on what they try to do and whether they start seeing successes or failures. It's definitely an art to do so, and no easy trick - but it sounds like that sort of improvisation is your style, if you are willing to simply run with it. The rules are in place to let you do so - don't be afraid to try pushing beyond the raw formulas, and see what happens.