However, avpicture_get_size is defined.
No, as the header (<libavcodec/avcodec.h>) just declares it.
The definition is in the library itself.
So you might like to add the linker option to link libavcodec when invoking gcc:
-lavcodec
Please also note that libraries need to be specified on the command line after the files needing them:
gcc -I$HOME/ffmpeg/include program.c -lavcodec
Not like this:
gcc -lavcodec -I$HOME/ffmpeg/include program.c
Referring to Wyzard's comment, the complete command might look like this:
gcc -I$HOME/ffmpeg/include program.c -L$HOME/ffmpeg/lib -lavcodec
For libraries not stored in the linkers standard location the option -L specifies an additional search path to lookup libraries specified using the -l option, that is libavcodec.x.y.z in this case.
For a detailed reference on GCC's linker option, please read here.