Wow, I actually get to post at the start of one of these things.
Anyways, here's my thoughts on Boadica of the Celts
1) With the Charismatic trait, this is one of those rare cases where it might be worthwhile trying for Stonehenge. When you get a Great Prophet, bulb theology for your highly trained Gallic Warriors.
2) Especially on Immortal, I wouldn't go for an early religion. Wait until someone builds a nice, fat, juicy shrine for you. Research your worker techs first, including bronze working. If you want a religion, try for either Judaism or Christianity. At any rate, plan on burning a great prophet for Theocracy, which is boon for Boudica.
3) Once the basics are out of the way, research iron working and construction.
4) While Boadica has one of the best trait combinations for warmongering, she is one warmonger who should bide her time. I'd concentrate on REXing first, that way you have your choice of victims. I'd wait until you have catapults. Once you have a stack of level 3 catapults and Gallic Warriors, with a few axemen and spearmen for support. Pick a fight with your neighbor, preferably the one that just built a shrine for you.
5) I've seen quite a bit of dissing the Celts unique unit, especially their ability to get Guerrilla III. I personally don't think they're looking at it quite right. Yes, City Raider II is more likely to win, but with GIII you have longer odds which yields more XP, without increasing your losses thanks to that 50% withdrawal chance. If you can produce GIII thanks to theocracy + barracks, they're only a single victory away from level 4 and CRI. Plus you'll get your great general sooner. Once you've got that Great General, you can give newer ones more traditional promotions.
5) Another advantage of the Charismatic trait: Barracks + settled Great General + Theocracy + Vassalage = Level 4 troops. IMO, with the Charismatic trait, you're better off settling your first GG in your heroic epic city, as opposed to the traditional MASH unit.
As for map type... I've fallen in love with shuffle. You never know what you're going to get, and Boadica performs well on any style map... except perhaps Archipelago.