How do skeletal animations fundamentally work? Are their runtimes considerably slower than keyfram animation? I mean, don't the vertex position data have to be "populated"/"generated"/"interpolated" at each render frame?

Yes, they are theoretically slower than vertex interpolation, but you often do the bone interpolation on the CPU (often only ~100 bones) and the vertex interpolation on the GPU (vertex shader). In this case you will have really fast and memory sparse animations.

Therefor, skeletal animations are the way to go in most situation (exceptions might be facial morph animations etc.).

Theoretically I think, that straight keyframe interpolation should be faster when done on the GPU, but not much (bandwidth/caching etc). The problem with vertex (morph) animation is, that it needs a lot of memory. Modern game characters have between 10k to 100k polys and >10k keyframes, this will consume a lot of memory, especially video memory if you want to keep the data on the GPU.

Simple example:

10k vertices main character with 5k animation frames (~xbox360/ps3 main char)

= 10000 * 12 * 5000 // vertex position = 3 floats = 12 bytes

= 600000000

= 572m

Compare this to

10k vertices main cahracter with 100 bones and 5k animation frames

= 10000 * (12+16) // (vertex position + 4 bone weights/indicies)

+ 5000 * (12+16) // one bone matrix = 1 postion vector + 1 rotation quaternion

= 420000

= 0.4m

~ 7% of the vertex animation version

Further on you can compress the rotation quaternion/ bone weights/indicies really good to further decrease the memory footprint.

But still to be clear, even with this bone/CPU, vertex/GPU "really fast and memory sparse animations" - they're still slower than just straight keyframe animations, yeah?

FWIW: there is the possible trick of precalculating the model frames.

then, rather than recalculating everything every frame, you cache the various precalculated model positions (for discrete frame-numbers), and then interpolate between these.

for example, in my case, I use 10Hz for the "basic" animation framerate, with optional linearly interpolated frames.