The parts of this answer dealing with victory in the general classification apply to any UCI-regulated stage road race that I'm aware of. The overall winner (aka the winner of the general classification) is, in fact, determined by cumulative time on all the stages, added up. However, there are three additional prize classifications: sprints and mountains, plus the classification for best young rider. On top of that, the individual stages themselves award prize money. There is also a prize for the top team, determined by the total time that the team's best 3 riders take; this is considered less prestigious than the other prizes, and isn't usually contested intentionally.
The Tour's Diverse Terrain
One of the key things to note is that there are a few types of stages. There are flat stages, rolling (aka hilly, but not mountainous) stages, time trials, and mountain stages (usually with one or more mountains, usually but not always finishing at the top of a climb). In the latter two stage types, the gaps between the riders competing for the general classification can be a lot bigger than you see on the flat stages.
The early part of all the three Grand Tours tends to be dominated by flat and rolling stages. Here, sprinters and breakaway riders tend to dominate. Time gaps tend to be small unless a small group breaks away and is not reeled in by the finish - this is not common (NB: but it does happen; Google Thomas Voeckler for one example of a successful breakaway specialist).
In fact, in all the Grand Tours, the last stage tends to be a flat one into the capital. It is traditionally more of a parade. It is won by a sprinter. Some exceptions have happened by design (Google the 1989 Tour de France for an example when the race was concluded with a time trial into Paris). I believe the last stage tends to be considered more prestigious. After all, it's in the capital among a large bunch of spectators. GC riders don't contest the final sprint stage (unless it's not a sprint stage), as they do not perform well in the sprints (due to specialization).
Games Within a Game
One of the nice things about cycling is that even during the same grand tour, there are multiple games within the main race. The mountains and sprint classifications are decided by points, rather than time. The first few finishers in a stage earn points in the sprint classification. There are also intermediate sprint points offering fewer points than the final sprint.
In a separate points system, points are awarded to riders who cross a summit first (NB: it's possible for a breakaway rider to collect the climbers classification points on multiple climbs in one stage; Google Laurent Jalabert for an example.) Moreover, each stage has prize money associated with it that is separate from the GC prize money. Riders who were trying to contend for GC may attempt a stage win to salvage their race somewhat; Nairo Quintana did this in the 2019 Tour. Some riders may even deliberately drop back on prior stages, so as to increase the time gap to the current GC leader. This decreases the chance that the GC leader's team will chase them. In theory, it's possible to win multiple jerseys. In practice, the last person to do so was Eddy Merckx in 1969, before professional road cyclists became much more specialized.
This is complicated very slightly by the fact that many stages award time bonuses to the top 3 finishers. Thus, the yellow jersey (i.e. the rider currently leading the general classification) frequently passes between riders who aren't real threats for the overall classification in Paris (example riders who have earned the yellow jersey thanks to early performance include the aforementioned Voeckler and Julian Alaphilippe; neither ever won the Tour, and it is not very likely that Alaphilippe can if he remains a breakaway specialist rider).
What Types of Riders Contest Each Classification?
What skills differentiate breakaway specialists from general classification (GC) contenders? The latter need to time trial well, and to climb well. In the Tour, I think conventional wisdom is that the better time trialists have the advantage; the climbs are not steep enough to let pure climbers (who tend to be poor time trialists) gain enough time on the time trialists. The reverse often appears to be true in the Giro d'Italia and Vuelta Espana. Riders who are better climbers than time trialists may aim for stage victories in any Grand Tour.
Breakaway specialists need to be able to execute and recover from repeated hard efforts (specifically, VO2 max-type efforts, or short bursts at 110% or more of functional threshold power; these can be sustained for one to five minutes). These riders will tend to aim for stage victories. If they capture one of the major jerseys, they often attempt to hold it for as long as possible. (Again, Alaphilippe and Voeckler have done this.)
Pure sprinters need to specialize in sprints, which are 30 second or less efforts. They will, of course, need the attendant bike handling skills at close quarters.
Why So Complex?
Why all these games within the game? I'm not aware of the history and reasons behind the evolution of the Tour. In the current era, riders tend to specialize highly, e.g. the people contesting Grand Tours typically specialize in this, and they train for time trials and extended climbs. This typically comes at the expense of their ability to contest many single-day races. The multiple classifications and prizes do seem to reward various types of riders, and to give them reason to enter one of the three marquee events. On the fan side, this complexity does seem to reward fan engagement. It is admittedly a large number of individual items of information to take in, but each individual competition is not that complex.
The starting order in non-time trial stages is not adjusted to my knowledge because it does not matter. At all. Because cyclists can draft each other, by the time the stage is over, anyone at the front of the start line had precisely zero advantage. Anyone who tried to ride in front the whole race would have been benefitting anyone behind them (NB: many GC contenders' teams will, however, take the front to prevent contenders from getting into a break). TT start order is the reverse of the current general classification, i.e. in 1989 on the final stage, Greg Lemond started the stage in 2nd place, and started the TT second last; the then-race leader, Laurent Fignon, started last.
In the proposed example, where Joe won 20 stages but Mark won the last by some margin, you are potentially correct to point out that Joe's perceived advantage should exceed Mark's. However, it depends on how much of a gap there was between Mark and Joe on each stage, counting any time bonuses in play. What we would want to know at the start of stage 21 is, what is Mark's accumulated deficit to Joe? At the end of stage 21, what is Joe's time gap to Mark, and is it bigger than the starting gap between the riders?
In the 1989 Tour de France, Laurent Fignon and Greg Lemond traded the yellow jersey back and forth repeatedly. Fignon led Lemond by 50 seconds on stage 20, which was generally considered to be enough for Fignon to prevail at the end of the race. In fact, it was not.