Martin. I love it, it's an ancient name, literally a variation of a name for Mars, the Roman god of war, which is why it's funny to me that it has a dowdy, "of its time" reputation to so many.
Also, you get the nickname Marty from it, which is lovely.
I don't know any Maximilians, but Max is getting a bit overused, in my opinion.