How to make a true linear quaternion rotation?
You would need to make a sinus/cosinus graph for that animation to have linear motion with quaternions:

For the 1st cube I set Euler rotation and animated a linear rotation, with Copy rotation constraint copied that to the second cube and then baked the animation on it with Object > Animation > Bake Action (visual keying on). This resulted in (the gif is little laggy):



This could be done easily with Sinusoidal easing type. Setting correct easingIn/easingOut for keyframes yields to this nice result: