Hi,
The cheapest we know of ourselves is SIPS ATOS. It's available for French banks. You negotiate directly with your bank and if you have a business model which fits their statistics, you can get rates as low as 0.5% per transaction (for european transactions, and 1% for outside EU transactions).
The most complete, is a complex question as it depends on your needs. PayPal is pretty complete with all its APIs. The Adaptive API for example, which allows to pay directly and automatically the vendors of a single payment made by the customer, is really nice for a multivendor store, and not a lot of payment gateways do that. It also have a lot of settings, features in the backend merchant interface. Among the ones I tested, that's the one I preferred regarding the completeness.
Regarding the reliability, any big payment gateway will be reliable. They have programmed shutdowns of all or part of their services for maintenance, but it's usually smooth sailing.