OK, 580 kbps is awful. Wait for FiOS then choose a new service, including looking at a higher service level of DSL. In meantime, check
http://www.dslreports.com/ for reviews on the different services, e.g. "fiber" "CA" and "FIOS" pulls up numerous reviews, most seem positive. No FIOS available in my area, so no experience to give you.