From your descriptions, it sounds like you may be using a low quality Shadow Map. Try going into the Lighting Globals panel and increasing the size of the Shadow Map. After doing this, the shadows should look a lot better.
Hope this helps. If you are still having problems, please send the project file to me at firstname.lastname@example.org and I'll take a look at what you are running into.