What should my MySQL Collation be when starting a new database and adding tables?

It depends of what you intend to put into and how you plan to use it.
Only 1 language, and that don't use accentuated characters, to go for an accent insensitive collation.
Upper/lower case is a non issue, then go for a case insensitive collation.

I am a dba, living in a country where we have 4 official languages with accentuated characters, and the collation I usually use in ms sql server is latin1-ai-ci (latin 1, accent insensitive, case insensitive).

I would use the utf8_general_ci collation.
As the mysql manual state:
http://dev.mysql.com/doc/refman/5.0/...entations.html

Non-UCA collations have a one-to-one mapping from character code to weight. In MySQL, such collations are case insensitive and accent insensitive. utf8_general_ci is an example: 'a', 'A', 'À', and 'á' each have different character codes but all have a weight of 0x0041 and compare as equal.
mysql> SET NAMES 'utf8' COLLATE 'utf8_general_ci';
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT 'a' = 'A', 'a' = 'À', 'a' = 'á';
+-----------+-----------+-----------+
| 'a' = 'A' | 'a' = 'À' | 'a' = 'á' |
+-----------+-----------+-----------+
| 1 | 1 | 1 |
+-----------+-----------+-----------+
1 row in set (0.06 sec)
UCA-based collations in MySQL have these properties:

• If a character has weights, each weight uses 2 bytes (16 bits)
• A character may have zero weights (or an empty weight). In this case, the character is ignorable. Example: "U+0000 NULL" does not have a weight and is ignorable.
• A character may have one weight. Example: 'a' has a weight of 0x0E33.
• A character may have many weights. This is an expansion. Example: The German letter 'ß' (SZ LEAGUE, or SHARP S) has a weight of 0x0FEA0FEA.
• Many characters may have one weight. This is a contraction. Example: 'ch' is a single letter in Czech and has a weight of 0x0EE2.

A many-characters-to-many-weights mapping is also possible (this is contraction with expansion), but is not supported by MySQL.

Great thanks!