Hey there, all.

I'm interested in what kind of gaming APIs you'd suggest for someone just starting out, trying to learn the basics of game programming. I am already an experienced programmer, I just don't know the tools or theory that I need to apply it to a game.

I prefer to work in C, Python, or Java. I'd also be interested in algorithms common in gaming and other paradigms if you have any references!

SFML and SDL2 come to mind.

Very powerful librarys that can handle input/video/sound/network/etc... that are easy to use and at the same time run on different platforms.

SFML is a bit more beginner oriented and gives more "higher level" tools. It is more object oriented then SDL2.
http://www.sfml-dev.org/learn.php

SDL2 is bit more powerful but still very easy to use. Especially if you compare it to the native platforms APIs that it wraps around.
https://wiki.libsdl.org/Introduction

Both come with many bindings for different programming languages.

For Python, have a look at pygame. I would also recommend browsing through the articles of this forum, loads of game-related stuff there. I once did, and found 60+ articles that look interesting to read. Now I only have to find the time to do that

Here is a free resource for game programming patterns: http://gameprogrammingpatterns.com/contents.html

Pretty much agree with the suggestions already given.

As you are already comfortable with programming then I suppose the best advice is to - of course - make simple games to start off with. Here is a suggestion of projects, in ascending order of difficulty...

1) A command-line text game. Like the pioneers of old, see if you can bring a world to life with just your language-of-choice. Remake it with a GUI?

2) Pong! Get to grips with an api such as SDL without putting your back out.

3) Asteroids. Step up to the mark with some basic maths - square roots, SohCahToa and vectors are your friends.

4) Gauntlet. So far you've made do with just code, but now you need a basic level editor.

5) Wolfenstein3D. Pretty much employing the maths of Asteroids with the level design of Gauntlet...with ray casting.

...and for each project give yourself about two to three months.

Not strictly an API but I would check Panda3d since you mentioned python.