How to animate Rubik's Cube rotations
You definitely need to use Quaternion rotation, but you don't have to use linear interpolation. If you set it to Bezier and set the handles to Automatic, then select all in the Graph window, then hit Shift+S, you can select Flatten Handles, which will help fix the problem of different cubies moving at different rates than their neighbors.

You should also add keyframes for all cubies whenever you record a turn, so that all the handles are the same widths. These two things together will completely solve your F-Curve troubles.

You should also move the individual centers of your cubies to the center of the whole cube, so they rotate correctly, and so that the only keyframes you'll need are those of Rotation.