Please note that some of the information below is as of 2013! Refer to this 2 later posts for latest tier and evaluation list from GameWith website.
Update #2: I managed to try out an account with Great Valkyrie. Now is a great time to get light monsters like Kirin as they are hard to level up and with the current Carnival of Light, they come out at level 30. I find the Healer team to be a little weaker than the spike teams (maybe I'm spoilt by the multiplier damage!) and although her team members are mostly farmable, I think it is going to take a longer and tougher time with her.
Update #1: "Found another useful guide in the PAD wiki talking about starting rolls and other useful starting information. The monsters are displayed in pictures and categorised so it is very easy to read and see everything in one glance. I agree with it except:
- Isis being in the top tier as her multiplier is quite low compared to the other spike leaders and her active skill is not that useful.
- Kushinada not being in the Challenge tier as high combos is required to get the higher attack multipliers to put her on par with the x3.5 and x4+ leaders.
- Echidna being in any category at all because she is farmable!
There are also 2 new Godfest-only monsters like the Odins, Red and Green Sonia. Each give x2.5 attack and recovery (RCV) to devil and dragon respectively and changes the whole board to their colours as their active skill. They have a very high cost (over 30) so you cannot put them in your team early but the Red one seems very strong base on the PAD forum discussion. This is what Goody has to say. It looks like she will make a good starter whereas Green will probably be more of a sub for Balanced team."
*The US version is currently in the midst of a 24hr God Festival so now is a good time to start the game as well as to reroll. Egyptian and Indian Gods have 3 times chance to drop from the Rare Egg Machine (REM)*
One of the most important part of the game is the first monster you get from the tutorial. For starter dragon, going with red is the best as a mono-red team is farmable from dungeons. If you did not get a good monster (mainly the god types), it might be a good idea to redo the tutorial from scratch again until you get a good monster to start the game. Refer to this reddit forum on how to reroll. It is mainly talking about iOS. For Android, it requires the phone to be rooted.
As to what monsters to aim for, there are 2 good resources from 2 different forums:
1) ggFTW Guide (Starting off), ver 5.1.2 The game is currently ver 6+ but the information is still quite relevant
2) Puzzle & Dragons Forum: [Beginner] Starting Rolls (Includes the new Japanese 2.0 gods and this forum also has a lot of useful information about the game)
To summarise from both threads, you will want to aim for Archangel Lucifer, or spike combo leaders like Horus, Isis, Bastet, Kushinada, Umisachi & Yamasachi, Okuninushi or a Chinese god. For mono-color team leaders, only Loki and Persephone are recommended. Currently, there is a Batman collaboration event and you can get a Dark/Dark Batman which also make a good dark team leader like Loki. If you get a 4* silver egg that is a Valkyrie, you can consider keeping her as she makes a powerful end-game Healer team. I did not know about it and erased that data!
Personally, I think getting one of the spike combo leaders also make the game more fun as they reward you for your skill in the game. They are also powerful enough for the endgame dungeons, with possible exception of Isis, who is not as strong. Archangel Lucifer is powerful and easy to build a team around but is essentially of a grinding gameplay where you try to survive to use his active skill. Most of the recommended leaders also have non-REM team members so it is non-in-app purchase (non-IAP) friendly.
It may be tedious to keep redoing the tutorial to get a good leader. You may want to settle with a 5 star monster and try out the game first and find out whether the game suits you and you want to invest more time in the game. Do note that you can also beat the game without the above recommended leaders: "How to beat the game as a (casual) non-IAP player". The recommended starting monsters just make the game slightly easier.
Advance rerolling strategy
I got this from the Puzzle & Dragons Forum people. There are actually some who roll a good leader and keep those accounts to roll a further 2-3 more times by clearing some dungeons to get more stones, before deciding to keep the account. If you get a few complementary 5* monsters, you should definitely keep it! However, be warned that this is even more time consuming but you will also have 2-3 chance of landing the recommended leader and be all set for the game.