If you haven't programmed a game before, I'd recommend that you start with Python and Pygame. Python itself is very easy to learn if you're already a programmer, so that won't be too much of a leap for you.
With Pygame, you spend almost no time writing "glue" or dealing with mundane low-level details like window management and sound setup - you'll almost immediately be programming game logic and in no time you'll be blit
ing left and right. What's more, it'll be very easy to get a prototype of your game running so you can start experimenting with the mechanics - I've programmed a simple little side-scrolling platformer in a matter of hours.
Performance
The performance of Python with Pygame is normally decent for simple games, though "smooth-scrolling" games can show poor performance, especially on Linux (in my experience, at least - pygame.display.update()
literally took 15-30ms per frame on Linux, and 4-5 on Windows with cheapo Intel graphics, though this was two years ago and the Linux Intel driver has improved of late). In addition, if you have physics/math-heavy code Psyco can give you huge speedups (20% - 200% in some cases), though you'll be limited to 32 bit Python on x86 computers.
Once you get most of the game logic worked out, if performance is still unsatisfactory, you could switch to C and SDL. Since you've already written the game logic, you'll just have to focus on dealing directly with SDL. Even that should be fairly easy - Pygame internally uses SDL, so the translation should be relatively straightforward.
OpenGL
Unfortunately, the above is only true if you're writing a 2D game - Pygame gives you basically no help for OpenGL. However, I would not recommend starting game programming with OpenGL. It can be pretty difficult to understand at first, so you'd be presenting yourself with two problems at once - first, you're trying to figure out how to get the game logic/physics/ai/etc. working, and then you're struggling to understand OpenGL. It is worth it to learn OpenGL eventually, but not to start with - better to start with the basics and go from there.
Cross-Platform Considerations
As far as cross-platform concerns - py2exe (for Windows) and py2app (for Mac) allow you to build individual executable files that include your dependencies (including the Python interpreter and Pygame); however, I do not think you'd be able to build your executables from a Linux environment (you'd have to be able to borrow a Windows/Mac computer for a few minutes, probably). For Linux, you'd probably just distribute a .deb that lists Pygame as a Dependency (and Psyco as a Recommends or Suggests if necessary).