Instead of just thinking "I need a background for this level", think about where your game takes place, and what one might naturally see in such a location. Treat the backgrounds as an opportunity to show the player more about the world, establish the mood, etc. You could even use the backgrounds to help tell the game's story, if it's got one.
That is to say, don't limit yourself to just bricks. Build the whole scene. It's more work, but it's the kind of work that makes a huge difference to the player.
