I have played with Austria, Russia, The Celts and dabbled with Spain. Oh and a short venture with The Shoshone at the very beginning of playing VP. Any other civ would be fine. Learning how to work religion into warmongering would be good. I.e. which beliefs are good, which are better and which are downright wrong even if they seem like they would be a good fit. Tie it in with a fairly isolated start for the best of both suggestions.
Now I play king/emperor so take my advice with a grain of salt.
I play warmonger wide (which most warmongers probably do) that means religious beliefs that scale are good.
I would say that you need culture, faith and gold and these can be accumulated in several ways.
I prefer shrines early in my first citys to secure a religion, and getting one early is very good.
My favourite beliefs are:
God of war, brings you a lot of faith, with raging barbs even better, this probably the best one if you play agressive enough.
God of protection for some culture and faith in capital with no improvement required and more with buildings I know I will prioritise, scales with cities and the extra healing is useful.
Faith+culture from forests/jungle and the one from mountains can be ok if terrain is in heavy favour for that in capital.
Inspiration and tithe are both good options, cathedrals is good if you don't get tithe, church is a workable culture alternative (two religious buildings is probably too much).
Holy law is awesome, mediancy for the per city yields isnt too bad.
Coucil of elders is not as good as it was but somewhat ok.
Zelotry is very good.
Crusader spirit and defender of the faith are both good, I prefer defender of the faith because it sucks to be up against.
The bad usually requires a resource and will stop scaling, or it requires improments that you get 30+ turns later.
Stuff that affect foreign cities are meh, you want to conquer those citys and convert them.
I have not tried order, I don't feel like I need it compared to what other options are available.
There are adjustments that favour certain civs, but as always, it also depends what is available.