Four Eyes are better than None

1. Going last in turn order in a 5-player game doesn't mean you're out of it after Turn 1. While the other players are getting buildings, jump on the merchant and first (or later) turn initiative. This will give you the money you need ($14 for going 5th, $5 for placing the merchant in the colonization space Turn 2 and $1+ for initiative) to buy TWO buildings in Turn 2 when no one else has enough to buy any. You can wait to place your last Turn 2 colonists on two build spaces (since no competition there) AND you have free choice of 4 new buildings compared to those who chose late in turn 1. I think this more than makes up for the fact you did not get a building in Turn 1.

2. I agree the Discovery mechanic is flawed. However, it is not without its fun and suspense. I usually use 4 colonist strength to discover the initial territories and 5 to discover the cards, thus minimizing the chance of not succeeding but still taking a small amount of risk. I like your idea of allowing half the colonists to remain in the Discovery box if the mission fails. I also have another variant idea worthy of consideration: If you have any colonists in excess of what it takes to defeat the natives on a card, you get to place them in the colony IN ADDITION to the one you're normally allowed. So if you go for five colonist strength for an initial territory and there are only 3 natives, then you get to place THREE colonists, immediately gaining the resource and qualifying for victory points without having to place any other colonists there. This also compensates for the bad luck when you send five colonists only to find a measly two natives with fewer VPs and gold. If you think that's too great an incentive, limit the colonists to simply the excess left over after defeating the natives (i.e. not include the normal 1 colonist). With this variant, you could send 6-7 colonists to the region, leaving those in excess of the amount needed to defeat the natives. This variant would put a greater emphasis on Discovery, making the game a better one in my opinion. Of course, it changes the game a bit, too. Still, those players putting too many colonists in Discovery leave juicy actions for the others. What do you think? I may post this in the variant section of AoE III.

By the way, I guess I'm more aligned all the way around with the rest of your group... I HATE Cosmic Encounter. My reasons? The game is over too quickly for my tastes and I simply HATE the allying aspect of the game. In the second game I played, 3 out of the 5 players "won" because they all simultaneously scored their 5th outpost. Also, while I agree the characters are fun, they change the rules too much for my tastes. There is so much chaos in the game that it's hard to manage any sort of strategy. And if you draw good cards and combos, it's nearly impossible to keep you from winning.

Why they couldn't have implemented some sort of bidding system to allow you to bid to go first is beyond me.

For me the issue is not about AOE 3 specifically but about the ability of a game group to veto a game.

And the short answer to this is compromise.

I am going to make some assumptions here.
You have a regular game group.
You play with the same people (roughly) and it is not a club so you are only playing one game at a time with that group.

What I've found about boardgaming is that someone's poison is another player's potion. Not very game suits every player. But there are a lot of games out there to choose from, and some mechanics suit me where others don't.

Appendix 1 in the rulebook does detail an auction system for bidding for turn order. It's labelled "for expert players only" presumably because the first couple of times you play it's hard to know what to bid.

I think the problem with scenario 2 is that some people might feel marginalised. Some might say that if you don't enjoy many games with your gaming group then you should find a new gaming group but that's not always possible. But if you're the outlier of a group, you may only get a game you like every 4th game whereby the other 3 choose games they all like and 75% of the time are playing a fantastic game. As such, you're spending the majority of your time playing games you don't really like, so why bother turning up?

For me the issue is not about AOE 3 specifically but about the ability of a game group to veto a game.

And the short answer to this is compromise.

I am going to make some assumptions here.
You have a regular game group.
You play with the same people (roughly) and it is not a club so you are only playing one game at a time with that group.

Lets play out two different scenarios.
1) Anyone can veto a game
2) There is no veto allowed - or "suck it up, smile and enjoy the game"

Lets look at scenario 1.
With veto allowed you may end up playing a game that everyone can half enjoy but no one really loves. And I think this happens more often than not.
Lets use game ratings as an example.
Everyone wants to play their 10 game, but someone in the group will think it is a 5 game, so veto. This continues until everyone agrees on a game that is usually in the 6-7 range for everyone.
The pool of available games diminish and are all within the 6-7 range.

Time for scenario 2
It's now your turn to pick a game. Go pick it. You save time by not making decisions about which game to play. You get to play a 10 game and someone at the table is really enjoying it.
So its not your turn to pick. To be able to play your 10 game, you need to allow others to play theirs so at this point in time, shut up, smile and do your best. Again someone at the table is really enjoying this game.

I suggest you talk about it with your game group and let them decide which scenario they want to use. We have been going with scenario 2 for about a year after doing scenario 1 for the first year. I much prefer scenario 2.

By the way, I guess I'm more aligned all the way around with the rest of your group... I HATE Cosmic Encounter. My reasons? The game is over too quickly for my tastes and I simply HATE the allying aspect of the game. In the second game I played, 3 out of the 5 players "won" because they all simultaneously scored their 5th outpost. Also, while I agree the characters are fun, they change the rules too much for my tastes. There is so much chaos in the game that it's hard to manage any sort of strategy. And if you draw good cards and combos, it's nearly impossible to keep you from winning.