When you look back on the scenarios you've enjoyed - for any miniatures game - what did they have it common? I feel that a scenario should be something more than just a pretext for combat. It should have some kind of narrative mechanic, something that impacts the feel of the session's gameplay. That being said, new mechanics run the risk of being gimmicky. You want substantive scenario mechanics that can change your tactics and priorities, without needlessly slowing or railroading gameplay.

Can anyone offer examples of scenarios (again, for any game) that they found particularly enjoyable?

I love scenarios because it makes games more purposeful. Conflicts isn't normally both sides pitch up and slug it out. Instead one side is trying to achieve some strategic goal through this tatical enterprise. Having a goal in mind makes you behave and play differently. An all out assault is unlikely to be what will work best in this circumstance. Scenarios that make you use things you might not otherwise choose are fun as it expands your approach rather than the reductive iterative approach to find a perfect list. Scenarios do not have to be balanced but they do have to cause tension, to me the key element in any game worth playing.

I'm in the process of designing some scenarios for a campaign tournament, and have been looking back on previous games as well. Being an old Warhammer 40K player, I've been looking back at some of the older scenarios. The problem is that they are objective based, requring the models to hold ground, which is very difficult to translate to the constantly moving starfighters. But I managed to find some of the ones I enjoyed and translate the essence of the scenario:

Ambush: a victory point based escape from one edge to the other (or one corner to opposite corner) with attacker setting up on each side. A classic scenario, that might translate very well as a surprise ambush on an imperial convoy, or an imperial ambush on a rebel scouting party.

Hold your ground/defend: another scenario I've enjoyed is the defense of an object, or holding an objective for X rounds. Placing a sattelite/crippled ship or similar at the center of the board with one side defending it. However this scenario would need special rules, otherwise the attacker could just swoop in and focus fire the objective, and care little about defending ships or taking losses.

I prefer a scenario to just "kill them all" play. Better than having an objective is a series of objectives. There are some games out there that use random missions for each side. These are kept secret and your mission goal may be totally different from your opponents.