Out of that list, I think Greece is the easiest to use. Their UA is pretty strong, but largely passive, which is good when you're just starting out. Their UUs aren't bad either; the Hoplite can be very useful for defense in case you have an aggressive neighbor and the Companion Cav can eliminate those pesky Barb camps pretty easily (just beware of Spear/Pikemen).
As for the others, they're pretty generic, which I think is good for someone starting out. As someone said about the Iroquois, they're relatively weak on standard maps since they rely heavily on forests. Now on say, an Arboria map, the Iroquois will shine.
In regards to the Shoshone, they're a good "second game" civ IMHO. Their bonuses are great for anyone, but once you've played a game, you know what's more valuable from the ruins and generally have a better idea about citizen/city management if tiles.
I'd also recommend China, which is arguably one of the stronger Civilizations. They can either steamroll with the extra Great General power and Chu's, or turtle up and be extremely defensive with extra Citadels and again, the Chu's. The early gold certainly doesn't hurt either, especially since it's rather hard to come by initially.
EDIT: I was also unaware that it would work with City-States and other Civs you had open borders with. Has that always been the case?