Things that you must learn anew are quite great. It gives you a sense of accomplishment and appreciation when you finally figure out how to do something that's been hindering you for a while. There is, however, something to be said for games that are *too* frustrating. WC has always had a decent mix.
I think the perfect mix of challenge, intuitiveness, fun, and good storyline, was wc2. You had to be a good flyer, you had to use your wits, and the story was really cool. I'd really have to say that that's my ideal WC feel. Even though the Concordia was the best (and, most likely, best upkept) carrier in the fleet at the time, it didn't feel too "new fangled".
And, enemies were challenging because you had to know how to use your wits to get them in your gunsights in the first place (Broadsword, anyone?), not because they could flagelate to stay out of your crosshairs.