Extremely underpaid, as Matwek already pointed out.
Erik, to give you an idea, the budget for the making of Street Fighter 3rd Strike was 8 million usd, of course this includes not only art but all dependencies involved in developing the game.
This is why your experience in Fiverr and Upwork was so bad, you are hiring people that have no idea of the real scope of a project with this requirements, as soon as they realize what they accepted they just end up delivering really low quality assets or just bailing on you.
To make the project viable you should make compromises on expectations, scope and style. Otherwise you will have here the same experience as in Fiverr and Upwork.
In the style and quality you are requesting 1000 usd will get you at most the design of 5-6 characters without any kind of animations.