...

My approach avoids the use of BGP, but not for the above stated reasons. As I said at the SF NANOG, it is hard to get transit providers to send a full BGP table, it is hard to accept it, and it would take a modified GateD that randomized destinations in order to keep BGP's path selection from leading 90% of your routes down 1/Nth of your transit providers. BGP was the wrong answer.

Were the majority of your paths going down one single provider because of a silly tie-breaker like the numeric value of the IP address of the peer,

Mostly.

or was it because that provider had a shorter AS path? If its the latter, where's the problem?

AS path elements are not indicators of path badness. a!b!c!d might be better than x!y!d depending on whether (a!b + b!c + c!d) < (x!y + y!d). Some of the links could be subrate T3s or SMDS or ATM whereas others could be FDDI or private multi-DS3 interconnects. BGP wasn't intended to be used this way, that's why it doesn't have an end to end connection quality / linkstate model.

If one provider has a better path and you aren't out of bandwidth on the connection to that provider, why would you want to take a different path?

Defining "better" when all you have to work with is BGP, is pretty hard. It turns out that, as in DNS, round robin is better than any definable static ordering.