If you're a BYU student you can use their facilities for free
- Richards PE Building - basketball courts, pool, weight room in the women's locker room, dance studios (?)
- Smith Fieldhouse - main weight room, indoor track (might be able to use that even if you're not a student), gymnastics room (can you use that if you're not in a class or on the team?), dance studios
Gold's Gym - Fairly small one on 460 N 900 E. There are 2 larger locations in Orem.
24 Hour Fitness - On University Pkwy kind of by the dollar theater but on the other side. They have a pool. The nice thing is that you can do it from month to month, whereas with Gold's you have to sign a contract.
Recreation Center - Pool, raquetball courts, weight rooms with nautilus machines and free weights - their website is here
Curves - 2 locations in Provo, 3218 N. University Ave and 1118 S. University Ave. their website with locations, numbers, hours is here
Powerhouse Gym - I don't know if this one is real.. but here's a number: (801) 370-0400
kickboxing gym - throwdown?