I'd like to have a simple purchase page where you select any one of three service plans. Choosing a plan should result in monthly automated recurring billing to your credit card.
Integration should be as easy as pasting a few buttons/links on our website (after configuring the parameters in a control panel somewhere).
What service do you recommend?

Paypal subscription buttons :)

If I'm reading the nature of your post properly, it doesn't sound like you want to do much work to get something up and running with say, a shopping cart, merchant account, etc, correct?
If that's the case, Paypal payment buttons is the way to go. Their site gives you the code to insert into your page once you tell the site what each button is for, it's price, etc.. That way, you can accept credit cards, e-checks, and paypal for anything you sell on your site. Just make sure you abide by their terms of service with what you would like to sell.
You don't really have to apply for anything, and they are well known in the industry for ease of use with the payment/shopping cart buttons.
<< removed response to removed post >>

Thanks PropspinMike. The salesman at PayPal told me the subscribe button wouldn't work, but I suspect he may have been trying to upsell me. He told me that the subscribe button was really just to create a one-time payment with no recurring billing, since I want to accept credit cards. Is that BS or what?

PayPal doesn't have 'salesman' as far as I know. They outsource the majority of their support to people that don't even understand the english language let alone the information they are reading off to you. A PayPal subscription setup would do what it sounds like it would do, exactly what you want:)
There is nothing for PayPal to "upsell" to you in this regard.

Thanks woods01.
I'm afraid it looks like the PayPal Subscribe Button results in customers having to register for PayPal. I wonder how much extra hassle that is and how much it would affect sales for our web service.

I use whmcs for recurring billing and it works very well for my needs

Most Internet Payment Service Providers (IPSP) / Third Party Payor (3PP) like (some versions of Paypal) and 2Checkout and electronic payment gateways will offer a recurring billing processor.
If you are in the United States, you have hundreds of merchant account providers to choose from, and probably over a hundred or so electronic payment gateways. Some of the gateways will charge extra for this service and some will not. It can be just as simple as sending over a couple of variables to the gateway and a recurring billing plan is set up.
Another gateway - Quantum (http://www.quantumgateway.com/) offers some other features as well. Keep in mind that you can choose an IPSP or a merchant account with an electronic payment gateway depending on your location.