UKOnline has been around for a long time and appears to have a good reputation.
Are you sure that you can pick up the service? It's apparently only available to a select few at present.
Tiscali offers 512kbps for £15.99 with a 30GB cap and 1Mbps for the same price but with a 2GB cap (enough for the average user).
Compare that to the price I saw in Tesco this morning for its 521kbps unlimited service of £19.97.