I need to move surfaces around the screen based on certain horizontal and vertical velocities. I need those velocities to be completely random. My idea was to generate random float numbers (in which I succeeded) and use them as the velocities. This way I could have many different velocities, never being too fast or too slow. The problem is: SDL_BlitSurface will only accept a SDL_Rect as the parameter to determine the new rect with which the surface will be drawn, and SDL_Rect is a struct made of 4 ints: two for coordinates and two for dimensions;
Resuming: How to work with precision when blitting surfaces on SDL?
SDL_BlitSurface is working with pixels, and unfortunately you cannot have "half pixels". You should still represent your objects' coordinates as float, but convert them to int when passing them to your SDL_Rect. Since your SDL_Surfaces will always land perfectly on screen pixels, your graphics should always remain crisp.
That being said, to have more precision, I guess you could switch to rendering quads in OpenGL. The hardware will be responsible for calculating the pixel color of your textures when they are not properly aligned with screen pixels, resulting in "fuzzy" textures, but at least you will have total control of their position.