Some RTS that come to mind, even if most of the genre lacks memorable campaigns.
Tiberian Sun was pretty good. Optional missions, some pretty difficult scenarios and timed/optional objectives that would trigger new objectives if failed, objective map expanding. Although the last one was also a flaw in one case because there is at least one mission where it should go to mission failed after it becomes unwinnable (guy you need to brainwash evacs from map if you fail to capture him after botching stealth) but doesn't which in that case was bad design. Not sure if that was ever patched. Compared to Red Alert, WC II or Starcraft (even with BW) the scenarios had far better design. There was stealth, there were hidden paths or scripted events that made things easier, missions played out differently if optional missions before them were completed, lots of missions where you had to do your best with limited forces and reinforcements and of course the ability to choose missions (which sadly got ditched with Firestorm and only returned in C&C3, which apart from continuity issues and cutscene cheese was not that bad). The environmental hazards such as ice braking below units, ion storms, tiberium, tiberium veins and mutants added a lot of flavour to the maps.
Starcraft: Brood War. Vanilla campaign was good, basically not that different from what they did in WC2 but with some extra twists to the formula (in engine custscenes, updating objectives). Having the campaigns all happen one after the other (and all canon) was definitely something new at the time though. To be honest after reading yesterday how many issues with SC they had before release, I can't blame them for doing just good. With Brood War the mission design improved and you could see this was more than just warcraft in space, mission-wise. Quite a few memorable moments in BW both in story and mission aspects.
Warcraft III. Optional objectives, lots of little secrets and some missions variation. While I still regret the direction they took with it after WC2 (gold upkeep thresholds? low unit cap? No oil and ships? At least they ditched their original Role Playing Strategy concept...) it is a very solid campaign.
Starcraft II: Wings of Liberty. It got stale in the expansions sure, they ran out of ideas for missions after WoL and you could see they put in less effort into them and they became formulaic (how many generic "defend for X minutes" missions does LoV have again? 3?). The upgrade buying mechanic was nice, the slight non-linearity as well, although I guess it was too hard for the masses to do a different mission line if a mission was too hard, so they railroaded it more so that a mission was only available when the blizzard approved unit selection was as well. Plot was epic cinematic space opera derp so whatever, but the missions were a proper challenge on brutal without feeling like bullshit and they had enough variety to make you want to play more (something LoV failed to do once again, although I found it better than HotS due to the campaign meta-mechanics with factions).
Earth 2150 and Warzone 2100, while Warzone did the main base and unit dispatching to battle map mechanic first, Earth utilized the concept better IIRC. You had an overall campaign goal, a campaign time limit and absolute freedom as to what missions you take and how much resources you devote to the goal versus the war effort. This sliding scale of overall goal versus resources for completing missions made it challenging, also it had the added bonus of Earth's climate changing the closer it got to the sun as the time limit was running out. Too bad Earth 2160 was forgettable decline.
Homeworld, persistent fleet and persistent resources, the ability to steal enemy ships and a memorable story about travelling the unknown towards home, with some really nice missions. While looking back at the game it is pretty clear how much more could be done with the campaign persistence concept or that branching would fit very well in it, it is still by far one of the best in the genre.
Tiberian Sun, Warcraft III, SC2 and Homeworld all share one good feature regarding mission design, they did scenarios that went well beyond the scope of "skirmish with a lower tech level and maybe some cinematics/story tacked on" or a "10-20 mission tutorial for multiplayer" with a story tacked on which are the usual approaches (Grey Goo comes to mind, but also vanilla DOW, vanilla COH, C&C: Generals, Supreme Commander and others). If you are making a single-player campaign there is no need to stick to the "competitive-friendly" unit roster for the AI (or for the player), throw challenges/puzzles at the player other than just being severely outnumbered or outgunned, create obnoxiously imbalanced enemy mechanics, make him think beyond cookie-cutter build orders out of online multiplayer or the multiplayer meta-game.
