As for the topic:

Star Control, which was mainly about 2D space battles one on one spaceships of different types, had a "strategy mode" where you moved your ships in turn-based fashion, so your enemy wold have to face your ships of the best type against his. The "campaign" consisted of several such scenarios, where you could play for both sides.

Its sequel, however, Star Control 2: Ur-quan Masters had "campaign" in a form of 2D scroller, where you would fly between star systems and then inside star systems and you could even land on planets. The whole structure of this mode was like non-linear RPG where you were meeting various races, negotiated with them, sometimes did quests and only in some cases you fought with them (the battles were the same as in the first game). Essentially the single player global mode was rather close to Starflight and not unlike Mass Effect series.

---
Also, are we talking about sequel as "part two" or in more general sense - the next installment in the series? In latter case I can name Ultima Online (should I explain why?).

Dino Crisis 2. From RE like gameplay with 3D camera angles to full action, also back to RE like 2D backgrounds.

Amusingly, GTA 3 is mentionned twice as a point of comparison with other 3D freeroaming games, but, unless I've missed it, not as an exemple of sequel changing everything.

Don't forget the Friday the 13th or Rambo movies.
Sequels had little in common with the first one.

Too lazy to check if any of these have already been mentioned :P

- Dune 1 (adventure) to 2 (real time strategy) comes to mind, though I've never played the first game.
- I thought GTA2 to GTA3 was too big a change, but was pleasantly surprised in the end.
- Commandos 2&3 to the abomination I don't even want to call by name...
- Simcity 4 (& societies if you want to include it) to the new always-online one. Still pissed off about that episode :\
- MAX to MAX2 was a massive change as well, but a big flop from what I've read.
- Fallout 2 to 3 of course, both of which I think are excellent (former more so)
- Dawn of War 1 to Dawn of War 2 was a very big change as well, but worked pretty well. DoW3 is yet another big change,
but after seeing what they did with Gabriel Angelos I'm not that inclined to play it :P

If you count non-video games, I could mention that Dungeons & Dragons 4th edition, to my understanding, is completely different from other editions of the game.

Duke Nukem 3D - the sequel to a crappy 2d platform/gunner turned out to be an amazing FPS.

There Came an Echo - who expected the sequel to a rhythm game to be a tactical RTS with voice control?

Heretic 2 - seriously, who thought making this a third person action/adventure game was a good idea? Besides, Hertic already had a sequel - it was called Hexen.

Doom 3 - I didn't mind it, but the change from a mindless shooter to a Half-Life wannabe was a bit jarring, you gotta admit.

HoMM IV - I heard it changed things so much that genre fans hated it, so they went back to the old formula with V. Haven't played any of the ones past III though.

Lands of Lore 2 is a lot different from the first one. Only a single character instead of a party, smooth instead of tile movement, random shapeshifting, not nearly as much fun.

The Curse of Monkey Island may have a lot in common with MI2, what with being top-notch humorous adventures. But there's no denying that the shift in art style and getting rid of the verbs interface was a hell of a change. Not necessarily bad, mind you — I favor MI2, others like CoMI more, but at the end of the day they're both awesome games.

What about Postal? I haven't played any title in the series, but I looked at the screenshots for Postal 1 and 2 on gog and had a hard time believing there was anything linking both games.

And I agree with Telika that it was surprising it took so long for someone to mention GTA3 as a huge shift from GTA2.

deleted

SaGa 3 is not only different from every entry in the series, but it even happens to be slightly nonliniar, at that.

Being non-liner is actually typical of the SaGa series; it's the early titles that are exceptions to that rule. In fact, SaGa 3 is very linear by SaGa standards.

Also, the game got a remake for the Nintendo DS (only released in Japan, but I have played it) that brings it in line, gameplay-wise, with other SaGa games. (Weapons and spellbooks have durability, MP and XP are gone, stats improve based on your actions, weapon and magic skills improve by use; the only major feature still left is the ability to change races via meat/parts (which are much more common in the DS version).)

Exactly! If you were not lazy, you would see my comment about Dune: The Building of a Dynasty not being a sequel of Dune, despite the nickname Dune 2. XD

I think OP said that 2D-3D transition doesn't count.

Actually, the only real big change was making heroes themselves to be separate units alongside usual creature stacks. Though that change completely broke the balance.

If it's a "natural" progression for the time, but Duke Nukem also changes gameplay, genre, and perspective from third person to first person. That's different from, say, Monkey Island going 3D but more or less staying true to the adventure gameplay.

Street Fighter II.

Does that mean that Postal 2, GTA 3, Wolfenstein 3D, Metal Gear Solid, Sonic Adventure, Castlevania 64 and Mario 64 are legit too?