I have personally found that the quality of foam varies greatly between different brands/types foam mats. Some vary in thickness from one end of a mat to the other by 1/8" easily (1/2" on one end, and slowly gets thinner to about 3/8" on the other).
I find that the cheaper mats are also less dense, making them harder to cut cleanly, and they wear out blades faster. I'm not saying you have to buy the most expensive ones you find, but midway on the price scale will get you decent foam to work with. I think I usually spend $15-25 for a pack of four (sale prices up in Canada). I have had the worst luck with the cheaper "diamond plate" style mats from princess auto (essentially harbour freight).
My normal go-to for mats are sold at Home Depot and Canadian tire and have very small texture marks on the backside. I really don't know how to describe them, but I'll see if I can link a picture shortly.
https://st.hzcdn.com/simgs/07c16adc0717e516_4-4373/contemporary-home-gym-equipment.jpg
The best mats I have used had a zig zag pattern on the back, were consistently 1/2" thick, and were very dense. Found them at Canadian tire for $25 (I realize that does t help you down south).
I would check out Home Depot and wal mart where you are. In my local wal mart, the mats are kept near the exercise equipment. If you need to ask for help, just ask an employee for the foam mats with puzzle shaped edges... No one outside of the cosplay community calls them EVA foam.
Edit: the other post above is talking about Costco... There should be one in your area. I believe you guys also have sam's club down there, which would be similar (it's been about 12 years since I lived in the southern states, so my memory is a little hazy haha)