Making numbers shifted is also potentially problematic for vim users, though I suppose it depends on how much you use them.  Personally, I use the low numbers quite a lot.

I think, by definition, the important feature of AltGr is that it's a modifier (like shift), giving additional layer(s) when you press it.  On some layouts, right alt is just alt, while on others, it's AltGr. 

Other keys can also be used to trigger the additional layer(s).  DreymaR's Extend layer uses Caps, for instance.

I would only worry about extra layers after learning Colemak; piling on too much at once makes learning stuff harder.  Speaking of that, be sure to take a look at Tarmak.

I've been testing remapping AltGr to right shift since I rarely use the latter.  However, many others would (I suspect) consider not using both shifts a bad habit.

It depends a lot on your selection of symbols and where you place your modifier.  For example, keys that are held down (e.g. arrows, backspace) should probably go on the opposite hand to the modifier.

Sorry, I don't know much about windows.  But I'd first strongly consider making caps into a modifier (whether Ctrl or AltGr-like), as it's one of the easier candidates to reach.

So my main two questions are: Which AltGr/Caps Lock layout would be the best for programming? And what do I have to do to make gaming work with colemak?

Sorry I came late to the party guys. Life... don't talk to me about life.

Ok, first off: ultimately davkol is correct. Nothing beats a customizable hardware implementation that lets you switch between layouts AND has support for multilayer.

For cost effectiveness and portability: Hardware Remapper.

For the best little split desk keyboard money can't buy: Ergodox. (Small, split keyboards, with thumbkeys makes this an awesome keyboard, and I've seen some truly amazing implementations. Downside: split keyboards make lap typing difficult, and, y'know, DIY. Lap typing is more ergonomic than desk typing; but increased mousing work means it may not be more ergonomic for general computing.)

For the best lap typing:

Your mileage may vary. ...also, don't ask about the touchpad.

For a gaming and general office friendly layout, I've been exploring this myself, with help from the MTGAP "Keyboard Layout Project" analysis tool. I posted some examples in my Improve Punctuation thread, before finding this one. I chose to put W-ASD on the Qwerty W-AS_F keys as the most reasonable compromise, but I can post others if you are interested.  (NOTE: I have not messed around with the programming aspect as editing controls and special characters are best left to other layers. Or, y'know, VIM. Likewise, many programming functions are best let to dedicated editors with language specific autocomplete, autoexpand, etc... or VIM.)

EDIT: I was trying to avoid being tacky and simply reposting something I'd written in another thread. In hindsight, if that thread is my own, redirecting people to that thread is probably even more distasteful. So, lesser of two evils:

W-ASeD: Colemakian + Mod.Punctuation Fix (alpha)
q  W  f  r  y    j  l  p  u  /
A  S  e  D  g    h  N  T  I  O  ;
x  c  z  v  b    k  m  '  .  ,


W-ASeD Optimized around Mod. Punctuation Fix (alpha)
q  W  f  r  y    b  m  u  p  /
A  S  e  D  g    l  N  I  T  O  ;
x  v  z  c  j    k  h  '  .  ,

W-ASDe Optimized around Mod. Punctuation Fix (pre-alpha)
q  W  r  f  y    k  g  h  p  /
A  S  D  E  u    l  T  O  N  I  ;
x  v  z  c  j    b  m  '  .  ,

Layouts based on most gaming and shortcut keys being Left of the 5th column. Also edited so ZXCV stays on the bottom, if not in order. Punctuation block remains in place, but is optimized with ShiftPairs locked together, for those who like to move keycaps. I also ran W-ASD on:
   E-SDF: Good stats, but puts E on L.Pinkie
   R-DFG: Even better stats, but uncomfortable reach for Shift/Ctrl/Tab when gaming
   E-A_DF: Awkward if you try to game with L.Ring on A. Might be good with Pinkie on A. Hope you don't Strafe Left often.
   AWD-S on WER-D: Just plain awful layouts.

I did not try WD-AS... maybe I should.

THE MOST PRACTICAL WINDOWS/MAC SOLUTION
   Tenkeyless Keyboard

      - Reduce keyboard to mouse distance, eliminate over-reach. Change layout to whatever you want, because it won't matter when you have a-

   Programmable Gameboard/Keypad

      - The core item in this solution. These devices are detected as different interface type from the keyboard, and as such, the settings do not overlap. Example here is the Logitech G13. Has 3 toggled layers called 'Modes'. Settings saved under 'profiles' for different applications. Up to 5 profiles can be saved directly into the device's memory. Set the 'default' profile Mode 1 to Qwerty for gaming, Mode 2 to numberpad, Mode 3 to standard shortcuts. The 4th Mode button is a quick Macro Record key. You really won't understand how useful one of these can be until you have one. (Logitech does not provide Linux drivers, but with the ability to store profiles on board, this should not be a problem as long as you have access to a Windows computer. Razer, the other main manufacturer of Gaming Keypads, does not provide Linux drivers either. Not sure how that one would work out.)

Bonus
   Programmable MMO-style Gaming Mouse

      - Put standard shortcuts on the programmable buttons, never use keyboard shortcuts or fiddly mouse gesture apps again. Probably even better for productivity than gaming. Unless your 'gaming' is EVE Online. Razer offers a Left-Handed version.

EDIT: To be fair, the competition:

Razer Orbweaver/Tartarus

The Orbweaver is the newer, more upscale of the two models. Both are smaller, and more ergonomic than the G13; the Orbweaver being somewhat unique having adjustable 'hand, thumb, and palm rest modules'. No screen (Logitech uses screen for various in game and out of game apps, such as System Performance Monitor, RSS Reader, POP3 Monitor, Clock and profile switching.). Mechanical keyswitches in the Orbweaver. Tartarus and G13 use membrane. Razer profile manager is cloud based, requires an account with valid e-mail address and wants to be online all the time (optional offline mode). The G13's manager isn't, but counters by allowing up to 5 profiles to be stored directly on the device, so you can still take it with you.

Orbweaver and Tartarus do not have 'modes' and have fewer finger keys than the G13; 20 and 16 respectively to the G13's 22. The thumbpad is not an analog joystick like the G13 (can be set as 4-way d-pad, plus down click), but a 8-way d-pad. Also unlike the G13, the thumbpads 8 directions can act as a modifier keys, allowing a whopping 160 or 128 (respectively) programmable commands, all right under your fingertips. Compare to the G13's 87 (22 finger keys, 2 Thumb Keys, 5-way d-pad, 3 modes).

Current Amazon Prices (USD): Orbweaver $93, Tartarus $76, G13 $56.

EDIT: Turns out Razer offers a Left-Handed MMO Mouse. Corrected entry.

I'm picking up a Logitech G600 and G13 soon, :)
Screw configuration utilities that require online accesss.
I've wanted them both for a long time.
The G13 screen is useless vapor though.