The Shoshone, Cultural Victory on Warlord in 1981. That said, I was 1 vote short of Diplomatic the previous time the vote came up...wasn't really paying attention though, or I could have paid gold to gain another city-state ally. Cultural victory would have been a lot faster if I didn't stumble across using tourism the hard way a few times...but that is why I dropped down to Warlord -- to really learn the cultural mechanic in a very forgiving setting. Now it is up to Prince to hone my fighting skills (my weakest area overall in civ), then probably up to my usual King level.