After a lot of research, I was able to find the source of the problem, and even though the playback is still a bit choppy (I get 17 to 19 fps for a 24 fps animation) it's way better than what it was.
The solution is pretty simple: reduce the Smooth Mesh settings of the rig's mesh. By default, the Smooth Mesh in the rig is set at "Smooth Mesh" (if you have worked in 3ds max, this is the equivalent of a Turbosmooth or Meshsmooth modifier).
|Default Smooth Mesh settings for the Ultimate Rig|
The only thing you have to do is remove the preview.
|New settings to improve playback|
To apply the changes through all the rig, select the the mesh main group in the outliner and press the "1" button in your keyboard.
|How to change the Smooth Mesh setting in all the mesh|
If this procedure still doesn't fix your playback problem, these are other things you can try :
Installing the latest Service Pack (download from the Autodesk Maya Support Page and follow the instructions)
Hiding the objects you don't need in the viewport (you can change layer visibility - Click on the "V" beside the layer name).
Make sure the renderer parameter is set to "Default Quality Renderer"
|Viewport Renderer menu|
Changing the update view setting to active viewport ONLY.
Reducing the size of the textures displayed in the viewport.
Using the default material.
|Use the default material|
I hope any of these tips help you. If you have any other solution that can improve the playback in the viewport, share it in the comments!