Utilising matrix nodes rather than constraints where possible is probably a plus.
Also, consider how Maya's parallel evaluation will interact with your rig, isolating dependency graph connections to minimise cross-evaluation will help (if part A does not require part B to evaluation make sure you do not have any arbitrary connections between them etc).
Also, utilise the DG Profiler. This comes with maya but is exposed as a plugin. Open the plugin manager and enable it. You can then access it via the Window/General menu. This will highlight the 'hotspots' on your rig and allow you to target them.
Finally, remember that Maya utilises a lazy evaluation method - it will not calculate everything in the frame, only what it thinks you need to see. With that in mind you may want to consider proxy representations which do not expose all the detail of the moment - perhaps a box representation of meshes parented under only the most obvious deformation points etc.
If you have a large number of nodes all involved in the same calculation you could be adventurous and compile the behaviour down to a single C++ node. Providing all the nodes are always being evaulated to reach the desired result this will also give you a speed gain. With parallel evaluation this will not help if only parts of the calculation are required each frame though.
All in all, start building in a way you're comfortable with and continuously run the DG profiler to find problem areas.