If your're bored with the clean-line look, you could go with something containing some photographic elements -- probably a banner at the top is a good place to start, rather than backgrounds...

Eric Meyer's site has a rotating photo banner. Ditto for Zeldman. Working out a system of slicing banners out of photos and rotating them should keep you occupied for a little while....

For a more designer approach, try something like Surfin' Safari with a striking colour scheme includinhg colourized photos. Some people loathe it, but that's a sign that it at least stands out from the crowd.

For a textured background, you could try something from Squidfingers