Edit: (VERSION 2) Added customizable settings! Footsteps now scale on foot size, change color on different floor materials and you can now toggle whether or not you want to see others footprints! Thanks to @ToldFable for suggesting these!
Edit: (VERSION 3) Added customizable particles and accelerated walking! Custom footstep sounds will be added soon! Please report any bugs you find to me, and tell me about any suggestions you have!
A Color3 Value is just composed of three different factors, red, blue, and green. As the value approaches (0, 0, 0) it becomes black and as it approaches (255, 255, 255) it becomes white. Luckily, Roblox has built-in a lerp function for Color3 values.
initialColor:Lerp(targetColor, alpha)
The following code, if used as needed, would interpolate the initial color to reach the target color based on the alpha. The alpha itself is from 0-1. Think about it this way, using an alpha of 0.5 would make the initial color 50% closer to the target color.
You can use this to your benefit to make the color darker, making the target color (0, 0, 0) and playing around with the alpha until it reaches your desired darkness.
This should be entirely client sided. On the client, you can detect a relatively precise value for their current movement speed by comparing the distances between each frame and dividing that distance by the delta time. From there, you can do the calculations needed to perform the footstep sounds.
This removes any unneeded replication, thus increasing your server performance.