Haha my players have taken an hour or more to pick combinations before. Personally I think it's OK as they will be stuck with the sand heroes for easily 20+ hours of game play, I would much rather they take long to pick a group they enjoy to play than to pick quickly and sit through hours of regret in a hero they do not enjoy to play.
Very good call. Depending on who's playing, we go down the random path of character selection as it players want to try out new characters with other players too. This never quite works out ideally, but hey, if you're going on an adventure of 9-11 quests, then you want to make sure everyone is happy. The same goes for the lieutenant selection too to a lesser extent.