How to ensure that two objects do not intersect before collision?
Short Answer: Switch the collision shape on each object to Box, and you're good to go.

Long Answer:

Poor collisions are generally due to a combination of a few things:

First is the precision of the simulation. Increasing the quality of the simulation should help, but this will slow down the simulation considerably. Usually you can get away without increasing the simulation precision.

Second is the density of the colliding meshes. A subdivided plane has more geometry to work with, and will collide better than a plane. In your file, adding 3 edge loops on the X and Y axes of the floor object gave the simulation enough geometry to run perfectly. This isn't always the best solution of course, as often times dense meshes are undesirable.

Final thing is how the collisions are being calculated. Blender has a number of different collision shapes that can be used. The geometric shapes (box, sphere, etc.) will always be the most stable as they are the most simple. In your case, both your objects are boxes of some form, so using box collisions will be best. Testing this confirms this, as switching both to Box fixes the collisions and the simulation is very stable as well.

The other types of collisions can work as well, and using the Mesh option (which uses the actual shape of the mesh as the collision object) on each object did give decent collisions, but they were far from perfect. Adding some more geometry to the floor object did help significantly though when using Mesh. Convex Hull (which uses a collision object that is always convex while still fitting the object as best it can) doesn't appear to work at all in your case, as it seems to do a poor job of determining a good collision shape for a box like object. Adding a bit of geometry and changing the shape to be slightly rounded made it work great though.

More information on the collision types can be found here (about halfway down).

It is almost always the best case to keep the simulation as simple as possible, and to use the simplest collision shapes possible so that Blender has to do the fewest calculations, which will also keep your simulation nice and fast.