To make something really feel different, you have a couple of choices: offer mechanically different options or change the cost/benefit choices of existing options in the game.
I'd be more a fan of almost going back to 2e varying xp rewards. If that's too much to contemplate (especailly considering how many people say they ditch xp anyway) then alter the achievable game mechanics such as when a milestone is achieved: Dwarves get a milestone upon drinking a pint, elves with a 30 minute quiet introspection, halfings need a good meal, and humans after every two encounters, for example.
The change in reward structure wil drive different behaviours for the players and that change is onservable behaviour is what really provides the appearance of otherness.
The trick is to make the make the variances different enough that the PCs will pursue different tactics and yet equally common/capable of being achieved.
Since fourth edition doesn't grant any powers at 4th or 8th level (nor 14th, 18th, 24th, 28th), how about getting racial stuff then?
I wouldn't change the milestones (which are a
party achievement, not an individual
character achievement); but how about these:
- = : Level 4 / Racial encounter powers: = -
Human: "Buck Up!" (No action) You may make a saving throw with a +2 bonus. This is in addition to any other saving throws you make. You may make this saving throw even if it is not your turn.
Dwarf: "Stay At It" (No action) You may convert one move action to a standard action. You may only do this on your own turn.
Elf: "Recheck" (Free action) Choose one Skill check that you have made during this encounter, or as your last action immediately prior to this encounter. You may retry that Skill check with a bonus equal to +2 (+3 at 11th Level, +4 at 21st Level). You must use the second result, even if it is lower.
Halfling: "Step Aside" (No action) You may convert one minor action to a move action. You may only do this on your own turn.
Gnome: "Despite Whatever" (Free action) You may make a Stealth check regardless of whether you have any cover or concealment.
Beliefling: "Curse It!" (No action) You may treat one unbloodied enemy as being bloodied for the duration of one turn.
Flagonhorn: "I'm Dangerous!" (No action) Any ally at least as far forward toward the enemy's position as you are gains flanking for the next attack it makes against an enemy adjacent to it, regardless of how far away you are from that enemy.
Mixed-breed (Half-Elf, Half-Orc, Half-Centaur, Half-Minotaur, Half-Deva, Half-Githzerai, Half-Revenant, Half-Wilden, Half-Shardmind, etc.): Consult with your DM to determine which of the above benefits is appropriate to your character, and gain that benefit.