Could you show some of the existing sprites? That'll help background artists know whether their work would be a good fit for your project without having to pester you :]
When you say "backgrounds/maps", do you mean those as a single entity (the maps the navigation takes place on), or as two distinct things, combat backgrounds and the navigable maps?