You have a good offering of styles and schools to check out. Since you are new, start with what is most convenient to home/work or lifestyle. Sooner or later time constraints will get in the way. If you have to drive an hour to class it is easy to start letting classes slide. Find a few schools who offer a trial class/course and take the time to give them all a chance. Talk to as many people (instructors, students, etc....) as possible to get a feel for the program. Speaking of programs; if they are promoting a black belt program that would raise flags for me. Websites are good and necessary but a crappy website does not automatically mean a bad program, and vice/versa.
Since you are open to style do not go in with any preconceived ideas. If you have specific goals and especially if you have any limitations be open and honest when you talk with the instructor.
Since you have no preference of style, can you expound on your thoughts of working out or goals? Maybe we can help.