Quite frankly, I don't see it as much of a problem. For one thing, the setting-shifting nature of the game is known up front, so the people who sign up are already the kinds of people who have varied interests, rather than the "I only play space marines" or "I only play mage games" people. For another, even if you assume that every player has a setting they hate so much they would ragequit over it rather than wait for it to change (a supposition I find unlikely,) there are many,
many available settings, and odds are they'd get quite a bit of playtime out of the game before they hit the setting that forces them out of the game.
I think the real challenge is making sure there's enough cohesion to make it feel like you're playing one character in a sequence of settings, rather than a series of independent settings with similar characters. Ideally, this would encourage the creation of extremely well-rounded characters so that the way they go about tackling their problems in internally consistent and appears to derive from the same personality. You'd want the Proud Warrior Race Guy to be a Barbarian in the Fantasy setting, Heavy Weapons Guy in the Space Marine setting, aggressive/forthright businessman in the Railroad Tycoon setting, etc, while the Sneaky Git is the Rogue in the Fantasy setting, Sniper in the Space Marine setting, and underhanded jerk in the Railroad Tycoon setting.
What you could do, is have a class system based on generic
Archetypal Characters, with their indivudual flavors/abilities altering based on sub-tropes of their new setting. This results in characters with a high amount of internal consistency, but also means that those characters are rather static. It also requires quite a bit of work on the part of the GM to try and get archetypes that are generic enough to translate to any setting, while remaining interesting enough to be worth playing- more troublesome is that some archetypes are rather genre-specific and difficult to translate, and that genre wouldn't be the same without the inclusion of at least
one character of that kind.
Another way you could tackle it is to have "Player Adjustment" phases, which are just a couple turns of mostly-RP where the player characters try to adapt to their new situation- the way they react determines what new abilities they gain. This allows for more dynamism in characters, at the cost of some continuity.
Alternately, we could just roll with the Fish out of Water scenario, and introduce a mechanic to gain new abilities without losing old ones. Abilities could be entirely genre-specific, with the only transference between genres being the player's ingenuity (The Barbarian lacks anything approaching management skills, so when thrust into Railroad Tycoon Land he compensates by using his strength to lay all the rails
himself.) Abilities could be tied to a generic skill tree, with flavor adjusting on a setting by setting basis.
Perhaps best-case, Abilities would be a combination of the two. Players are spirits hopping from body to body at the whim of some cruel fate/curse- they gain innate benefits depending on their host (magical ablities, great strength, wealth, etc) that are tied to the specific host, and do not transfer between bodies. Certain mental/spiritual abilities, however,
would carry over from situation to situation (business acumen, battle expertise, talent at making things.)
And now that I've been thinking of it for a while, nested random setting tables! Roll on the Main Table, then roll on the indicated tables.
Main Table1- Fantasy
2- Historical
3- SciFi
4- Adventure
5- Western?
6- Roll Twice
Fantasy Table1- Grimdark Fantasy
2- Fantasy Medieval Europe
3- Magic Land (fairies and Discworlds)
4-
Wuxia5- Horror (Fantasy Lovecraft)
6- Epic Fantasy
Historical (alternate or otherwise)1- Pre-History
2- Ancient Times
3- Medieval Times
4- Age of Sail
5- Industrial Era (American Civil War-WWII)
6- Modern/Future
SciFi1- Steampunk
2- Cyberpunk
3- Planetary Romance
4- Space Opera
5- Time Travel
6- Post-Apocalypse
Adventure1- Swashbuckilng Pirates
2- Safari
3- Tomb Raiding
4- Airship
5- Gangsters
6- Roll again, and also roll on Main Table again- merge results
Western1- Old West
2- Samurai Western
3- Space Western
4-6 Others I guess?
Alternately,
I pitched a Mad Lib idea a while back, and it would be amusing if waitlisters supplied the words.