What are these weird shadows and how can I get rid of them?

Are you using baked lighting? It could be that the resolution of the shadow maps is too low, so the shadows are bleeding out from under various objects.