NetFlix
Evan also mentions NetFlix. This is one of my favorite net companies. I've been using them since I got my DVD player, almost two years ago. Their customer service is pretty good. The only problem I'd have with them is related to what Evan likes so much about them. I live in Boston and it takes an extra day or so for dvds to get back to them. I'd love to see an east coast distribution center for movies so that your service level isn't reduced by living further away from them.
To add to his list of netflix-like place that offer adult fare. A friend of mine recently mentioned XRentDVD. One of these days I may get around to trying it out.