Hey guys! I went to FSU for undergrad, so fire away any questions you have!
Plenty of people go carless in Tallahassee - FSU has a pretty decent free bus system. It only goes to certain apartment complexes, so if you decide to go this route you will probably be living near undergrads. I think there are city buses as well but I don't think it's a super great public transportation system outside of FSU. Here is the FSU bus system: http://transportation.fsu.edu/maps/seminole-express If you click the real-time link you can see a map of where the buses go. It's definitely way nicer to have a car, but I know lots of people who didn't for a few years and were fine.
I had lots of fun in Tallahassee but it's definitely a college town, despite the presence of the capital. I would say avoid living south of campus for safety. I never felt unsafe really anywhere but property theft definitely does happen. Like many college towns, the farther away you live, the less undergrads will be around. So it just depends what you're looking for. I happen to prefer renting individually owned townhomes/houses rather than apartment complexes but if you have a preference I might be able to make some suggestions. Cost of living is generally really inexpensive and housing is pretty easy to find, but it definitely helps to look earlier. Killearn would be the really nice area (but farther out and pricier) where a lot of the professors live. There's a lot of restaurants/bars/shopping on N Monroe St and Thomasville Rd and that area is a pretty cool place to live, especially if you want to be near the interstate. If you don't want to have a car, I might be able to give some better recommendations if you have a price range? I lived in the Timbers on White Dr for a couple of years. The townhouse was older but huge and pretty inexpensive, and there were quite a few grad students in the area. It was biking distance but probably not walking, and the bus stopped over that way. It's not that close to many places you might want to hang out outside of school though.
Happy to answer any other questions!