I see that avatar resizing requires the GD module, which I understand has something to do with the GD library.
Now, I'm a ultra noob at this kind of stuff, how do I get the GD module installed? Do I just install the GD library? Where can I find the best installation instructions for that? Do I have to mod it somehow to get it to work with SMF?
I'm using linux/apache 4.3
It's usually installed with php.
Execute a phpinfo script and look for GD. If you don't have it, ask your host for support. BTW, if you are running PHP < 4.3.9 you won't have GIF write support. If you are using PHP < 4.3.11 your host needs to upgrade because of various vulnerabilities.