1. Try a minimalistic but stylish approach to art.
Knytt stories is a great example of this, the graphics by themselves look very simple, like a few pixels, but when the sprites, backdrops, and tiles come together it forms one cohesive stylistic piece of art that wouldn't be an exaggeration to call beautiful.
2. Create a really interesting and/or unique game with placeholder graphics.
If the game is special enough to catch someone's fancy after playing a small demo, it might be exactly what an artist was looking for to contribute his art to.
3. Using photoshop on photographs.
If drawing isn't your forte, I have seen people use the effects in photoshop to manipulate real photographs to create video game art with
4. Finding copyright free art.
like you said, there has to libraries of sprite art out there, I'm not exactly sure where, others could probably suggest popular websites