Looking for a payment gateway
It sounds like you want something like Worldpay or even Google Checkout. But it all depends what your turnover is, because these sorts of providers (who host the payment page themselves), tend to take a percentage of every transaction, rather than a fixed monthly fee that you can get from elsewhere.
The other thing to consider is, if you have any way of taking orders over the phone, and the phone operators need to take customers' credit card details, then your whole internal network will need to be PCI compliant, too.
If you JUST need it for a website, then that makes it easier. If you have a low turnover, then check out the sites mentioned above. If you have a high turnover, then it may work out more cost effective in the long run to get PCI-DSS certified and still keep control of credit card transactions in-house, giving you more flexibility, and cheaper transaction costs.
I'm looking for a payment gateway company so we can avoid tiresome PCI-DSS certification and its associated expenses. I'll get this out the way now, I don't want Paypal. It does what I want but it's really not a company I want to trust with any sort of money.
It needs to support the following flow:

User performs actions on our site, generating an amount that needs to be paid.
Our server contacts the gateway asynchronously (no hidden inputs) and tells it about the user, how much they need to pay. The gateway returns a URL and perhaps a tentative transaction ID.
Our server stores the transaction ID and redirects the user to the URL provided by the gateway.
The user fills out their payment details on the remote server.
When they have completed that, the gateway asynchronously contacts our server with the outcome, transaction id, etc and forwards them back to us (at a predestined URL).
We can show the user their order is complete/failed/etc. Fin.

If at all possible, UK or EU based and developer friendly.
We don't need any concept of a shopping basket as we have that all handled in our code already.
We have (or at least will have by launch) a proper merchant banking account - so cover services like Paypay aren't needed.
If their API covers Python (we're using Django) explicitly, all the better but I think I'm capable enough to decipher any other examples and transcode them into Python myself.