Yeah, specs for the PS1 are hard to really nail down. I think the performance of that system was largely dependent on the software it was trying to run. Just looking at screenshots I'd say that the average character had in the ballpark of 250-400 triangles. It's hard to really know for certain. A lot of the 'limitations' on that system were probably just the result of the technology and the techniques being so new. I mean, obviously it can only do so much, but according to some of the numbers I've seen, there are games that came out on the system that sould have been impossible. I doubt Sony even knew exactly what that sytem could do. Seems like every 6 months or so a game would come out that was previously not possible on the system. They even made a big deal out of crap games like "Blasto" because it streamed the levels off the disc on the fly. It was revolutionary at the time (tho also not that fun...), and the levels did look fairly decent sometimes. Probably a lot more geometry going on in games that did that.
And I don't know about 16 colors per map, either. I've been looking at some other games - some of the later FF games and RPG's especially - and some of them seem to have used more that 16 colors per map. FF9, for instance... lemme find a texture real quick...
http://www.spriters-resource.com/psx_ps2/finalfantasyix/index.htmlJust checking the Zidane texture, there are well over 400 colors in use. I'm going to assume that this is for the battle mode models, where they are more detailed. The resolution is odd as well. Looks like 128x192. Dunno how common that was. It could also be a 128x128 and a 128x64. I honestly don't know how the system handled something like that, but it couldn't have been an easy feat or more games would have used textures like these. I'm assuming that there was some some bit of code that square used to shoehorn several of these into the PS1's memory at the same time. If you cut that into two textures then it looks like each sheet might have an 8bit pallet, but both would have their own pallets... I'm too lazy to check

, but that's how it looks. It's definitely more than 16 per sheet, tho. The backgrounds seem to throw off that limitation as well:
http://www.mobygames.com/game/playstation/final-fantasy-ix/screenshots/gameShotId,25059/If I had to guess from that game alone, I'd say that you could use 128x128 textures as a max size with a unique 8bit pallet for each. That doesn't even sound possible on the system, but apparently FFIX did the impossible.
It might look more 'genuine' to limit to 16 colors or 24 or 32 or whatever, but those limitations seem to have been defeated by the last couple years of the system's life, as there were several other games that used more colorful texture sheets. The later FF games, Vagrant Story... I generally just paint and don't worry about it. You can always reduce to 8bit later and then clean it up a little.
Also,
http://www.mobygames.com/game/playstation/vagrant-story/screenshotsVagrant Story. That dragon thing in the second shot there has to be around 400 or more tris. The main character probably has a similar count. Guessing from the screen shots I've seen, I'd guess very DS-like limits. Like 2-3k on screen at once... maybe 3 or 4 times that in a scene or level or whatever... I wonder what the tri-counts were for games like Gran Turismo...
But yeah. There are papers all over that i've read that say the PSone can push this much or have this size max texture, etc, but then I'll stumble onto some screenshot or something that will defy those numbers. It appears like you could get away with a lot if you knew how to cheat the system a bit.