While I am somewhat fond of PoundTeam.com (if you read my signature, the reason is obvious) ... The BEST host for Vicidial is and has always been Vicihost.com.
That being said, if you prefer a standard Colocation facility or server hosting facility, note that Goautodial had instructions for installing Vicidial over "Stock CentOS". Not sure if they are up to date, so post back here if you try it and it still works. Same with Carpenox's instruction set. Come back here and post if you use it and offer your experience for the next poor schmuck who doesn't have enough bandwidth directly at the office to self-host.
After all, the software is free. It's the least you could do, right?