I think the best way to get replay value out of a game is to design it so that you can accomplish the objective by using multiple strategies.
"A game is a series of interesting choices" -Sid Meier
The more "weird" the strategy, the more interesting it is to me.

The problem with some RPG's and some FPS's is that the story line is linear and character progression is also linear. The linear nature of those games puts arbitrary restrictions on what strategies you can use and usually one particular strategy is whichever is strongest. Strongest strategy is not necessarily the most interesting strategy.

I like to think of "Magic: The Gathering" as a very well designed game. It's got tremendous replay value because of its versatility. There are TONS of interesting ways to defeat an opponent. My favorite strategy is to make my opponent draw dozens of cards at a time causing them run out of cards. If you run out of cards, you lose regardless of your health. It's just so weird and unexpected.
When I played Starcraft 2, my favorite strategy was to play zerg and mass queens, spine crawlers, and overseers. It's another weird and unexpected strategy.

So, I'd say that to really get the best replay value out of a game, you have to introduce lots of mechanics which can be combined in very interesting ways. Some games just don't lend themselves very well to that. An FPS can only introduce a few different types of guns, which mostly do the same thing: Shoot stuff in different ways. The "replay" value from an FPS comes from the twitchy skills it takes to shoot quickly and accurately and competing with those developed skills against other players. It's moderately interesting, but doesn't require a clever mind to thrive at it.

I think the campaigns are usually fun, even if they tell you everything you need to do (movies are fun!) but the problem is that the multiplayer side feels like a quick addition to the game.

I think most people spens their time in multiplayer, not in the campaign.

So, the campaign should be multiplayer. It would be nonlinear and the progress would depend on how a certain "chapter" in the story went from the part of everyone who played it. For example on server 1, there could be a game running for a day or 2, with an objective to capture a fortress (which would take a day or 2) . If the players can capture it, the next chapter is advancing to enemy bases. If not, it might be falling back to the ships and defending against enemy planes and whatever.