I agree a T1 line through a serial interface sounds like a good fit, you might even be able to get by a with a fractional T1 and save some money. You can contact your telco company they usually provide good support for getting customers setup on T1 lines. have a look at the link below for more info.
