Here's some weaknesses I've noticed that the natives DO have (both from playing as and against):
No artillery, except for the Iroquois, meaning that they have trouble taking down a well-fortified and defended (can't rely on buildings alone to defend your base) base or forward military base.
Weak defenses: They only get War huts (and in the Aztec's case Nobles huts as well), and on top of that the Souix can't even build WALLS (they can basically be thought of as AoE III WC equivalent to the Goths from AoC)... Basically a good mixed army with a team of about 6 Heavy cannons or Mortars can reduce a Native's entire frontline defenses to rubble in a matter of minutes, which, when your army rushes through the gap, will spell doom for the rest of their base as well.
No Factories: Big one here; No hvy artillery for free resources for them, which puts them at a bit of a disadvantage, economically in the IND age and later.
They also get the fewest Economic gathering upgrade cards as well (no royal mint, few, if any plantation or farm cards, etc)
In addition, here are some civ-specific weaknesses I've noticed:
Aztecs: See above post plus no artillery of any kind
Iroquois: Their hand cavalry (i.e. their only defense against massed artillery) is expensive and one of, if not the weakest in the game (My germans UHLANS outlast my Kanya horsemen when I send them to take out artillery)
Souix: No artillery at all, and no walls plus a rather weak economy (although the Earth Bounty card counterracts this a bit)
In addition, I find that concentrating on killing any native's Warchief as fast as possible during the initial engagement can turn the fight in your favor, since his aura will no longer be boosting nearby unit stats... Mercs also tend to be really nasty against Natives (especially since they cannot train any of their own), particularly Ronin and Highlanders.