I have been pondering like yourself. I've always chosen the fire starter first. Back when it was hardcore to start with a Charmander in Blue. But since I had Emboar in Black I was going to use Samurott as my starter, as I despise the grass type*. Too many weaknesses, not enough pimpsmacking. But like you, I've decided to take Keldeo over to my squad, which means I'm going to have a grass starter. It's going to be fun...
*Also since it was technically impossible to get a decent water Pokémon during the game since you got given the Super Rod after completing it. Which is why I had Carracosta as my fossil choice.