Ability Scores: +2 Str, -2 Int
Size Large: -1 to attack rolls and AC, reach 5', +1 to CMB/CMD, use large weapons
Racial Traits: darkvision 60'; natural cunning (+4 to Perception checks, never flat-footed, never lost, immune to maze spells and similar effects)
Natural Attack: 1d6 gore (2d6 if made as a charge attack)
Special: minotaur PCs do not get a 1st level feat (they still get any class feats)
The idea here is to create a race that's playable at 1st level, but could be comparable to a standard minotaur by the time it reached Ftr 6.
Large size is a huge benefit for melee characters ... even a relatively pedestrian longsword does 2d6 at size large. Go with a more traditional two-handed battleaxe and that 1st level minotaur would be doing 3d6+Str mod damage. This is why they sacrifice their 1st-level starter feat.
Whattya think, sirs?