They need to be careful with negative bonuses, but I think it could work and it could be fun.
Teuton’s “knights are 10% slower” is implemented via a missing technology, and I think a civilisation with “archers are 10% slower” would also work (depending on the design of the rest of the civ)
Civ nerfs which are too extreme, such as those sugested by @Kamandaran probably wouldn’t be fun. But I won’t claim to be certain.
I designed a civilization with a rather strong negative bonus a while back, and though the discussion exposed some flaws I think it could be made to work:
Civilization idea: the Elves