Ok, every town I go to and just venture out in to the 'wilderness' I get ambushed by Hired thugs, or assassins. I kill them every time but it is really annoying, and lydia is still with me and I've commited a few minor crimes but always paid my bounty. What's HAPPENING?!
The assassin is a random encounter. Starting from level 5 according to the wiki.
The thugs are because you stole stuff. They are going to teach you a lesson, your actions have consequences in skyrim.
It is all part of the radiant quest system. Search for it on the wiki.