GlassJaw said:
Cite the system you would use, general premise, setting, any particular house rules or things you would change, etc. (it doesn't have to necessarily be 3.x or even fantasy)
I would like to suggest some general guidelines instead
If you want something new, and you choose to follow the homebrew route, I'd say change
something, but don't change
everything. You may decide for example to change one or more of the following:
- character creation options
- technology level
- world ecology
- religion/alignment
- location type
- rules
For example, a simple thing to change in "world ecology" (and "c.c.o." as well) is races. You may just have an approach like this:
1. start with the 7 PHB races
2. choose some of them which don't exist in your world, and take them away
3. add other races from monster books
4. modify the races role in the world, their culture and eventually their stats
5. decide which of the the races are allowed to characters
In this process you may even want to base your decisions on what is cliche' in D&D and change it. Do you usually see too many elves and dwarves? Ditch them from your world entirely. Find a couple of underused evil races and make them the most important in your campaign: e.g. no more orcs and undead (either they don't exist, or they're unimportant), main villains are yuan-ti and rakshasa. Just a few changes like this are guaranteed to make your setting different than usual.
Going further with the changes to character options, you may try to rearrange core classes (removing/adding), to restrict some classes to higher levels, to limit PrCls to a small group of selected ones... lots of options.
Another possibility is to change religion issues entirely. Don't just bother to write up new deities (i've done it before, it's a waste of time game-wise). Consider instead some structural change: maybe your world is monotheistic, duotheistic or animistic. You may want to adopt a religion like in Rokugan for example. You may strengthen the link between magic and religion (everyone's spells come from a divine source) or cut it off entirely (that of priest is a job, completely separate from the cleric class which becomes just a different type of arcane caster).
Then you can change something in the technology level. This is not an easy issue however and I don't think you should design it yourself. But if you have a d20 book about firearms, steamworks, clockworks, air vessels or magic-as-commodity you can try adopt it in its entirety. Usually just one of these options is enough to complicate the game a lot.
An easier choice may be the "location type". Try setting the campaign on the open seas, underwater, underground, on high peaks, airborne over the clouds, on shifting landmasses, in hell, in ysgard, in the world serpent inn or something else. Otherwise, just pick up a couple of striking features for your world, with mostly just an aesthetic consequence: colossal trees, flying mountains, blue snow, talking winds....
Finally, you may change a couple of rules. Beside small changes, you may consider one or two big shifts (UA is full of them). Just browse UA's later chapters: weapon groups, recharge magic, armor as DR, spontaneous metamagic... These will definitely create new strategic issues that your players may find interesting.
In conclusion: those are endless options, but in practice you need few of them to make your setting very different, and easily your players will remember it for years. If I randomly pick just one-two ideas from each category above look what comes out:
- only Humans, Gnomes, Halflings plus Lizardfolks (more water-oriented) and Aaracockra
- main villains are Yuan-Ti (a lot everywhere, from weak to powerful), with Rakshasa being their spiritual counselors
- Fighters, Barbarians, Paladins, Rangers, Bards, Clerics are out; Swashbucklers, Favored Souls, Hexblades are in; no spellcasters before level 4
- religion completely free (believe what you want, that won't change your PC's abilities); most common faiths are dualistic (good deity-evil deity), druidic (no deities) and animistic (spirits)
- introduce a small book of firearms: they've just been invented so they are expensive and unreliable
- world is full of rivers and lakes, landmass/oceans scattered -> more importance to naval transport and activities
- when the wind blows strong in this world, you can hear it speak (main hook for the animistic belief)
- use Defense Bonus and Weapons Groups from UA
That will probably result in a slight swashbuckling-pirate feeling overall.
I just made it up on the fly while typing, to show how easy one can come up with simple ideas to make a setting different to what your group has been playing so far 
