If you already own your IP block and an ASN, you should not have much trouble finding an ISP that can speak BGP with you.
This is not really time consuming at all and should be fun for a backbone admin, but sometimes depends on the provider's upstreams, if they accept new prefixes without prior approval. I know from Level3 as an upstream it can take a few days before they accept a new prefix.
I think the recommendation of CH-Shaun is good :-)
██ • Dedicated Servers in Europe and Asia: http://www.server.lu • ██ • SINGAPORE and LUXMBOURG Servers with IPMI • ██ • Peering @ AMS-IX, DE-CIX, LINX, FRANCE-IX, EQUINIX SINGAPORE-PARIS-ASHBURN-CHICAGO-DALLAS-PALO ALTO-LOS ANGELES and LU-CIX •