Maximus was one of three names we were seriously considering for my son when he was born. We were debating between Wolf, Maximus and Luther. Luther won. Anyway, I like a lot of the names in your signature and I think we might have similar tastes. Maybe not, but I would suggest most of the boy names in my signature!
My favorites would be:
Of the names in your signature I like Damien and Dante a lot with Max. Maximus is such a strong boys name, and both Damien and Dante give me kind of the same impression.
Leonides - I like this one. Maximus and Leonides are two super awesome, strong boys names, and Max and Leo are their cute nn's!
Magnus - too similar to Max?
It depends on how you want to go, I think. I like Maximus with Lucius or Julius, but I don't know if that strikes you as too matchy. I also see it with other Roman type names - do you like the idea of having a Roman theme?
What about ...
Cyprian (one of my favorite names!)
Urban (another one that I think is just awesome)