I'm about 4 hours in (just got the dragonstone) and I want a companion, where can I get one this early in the game?

After killing your first quest dragon the Jarl of Whiterun will assign you one.

you can get one in riverwood by helping out the guys that are both in love with the girl and want you to give her a letter. I had the elf guy from riverwood, til i got HouseCarl.