You for sure want isolate the foot falls. Putting the treadmill on vibration isolation blocks will make is softer for you and reduce the noise too. The problem with the off the shelf ones for machinery is they are not big enough if your treadmill has incline/decline, as the wheels will move.
Look on Craigslist for "rubber mats" in the "materials" section. If you find these mats for cheap/free, you could also hang them or mount them to the walls, but for sure put a few layers thick under the treadmill.
Sound reduction is really all about mass and rubber is heavy, and flexible.