There are obvious places to look, like in taverns and guild halls, but then there are sometimes subtle places to look like ancestral tombs.
If anyone could provide me with a list of all the companions or even just a handful off the top of your head that were hard to find, that'd be great.
I'll throw in a few as well. Don't worry about specific names either.
Companion List:
Starter Companion - Seyda Neen
Undead Warrior - Samarys Tomb, (near Seyda Neen)
Altmer Knight - Balmora,Lucky Lockup
Ex Ordinator - Balmora, Eight Plates (top floor)
Redgaurd Mage - Balmora mages guild
Darkelf Archer - Balmora, Fighters guild
Breton assassin - Balmora, Morag Tong
Dark Elf thief - Fork in the road between Balmora and Caldera
Lich Wizard - Indalen Ancestral Tomb, Outside Caldera
Paladin - Fort Buckmoth(shrine)
Khajiit Archer - Vivec Foreign Quarter, Plaza
Breton Skirmisher - Fat Leg's Drop Off, Hla Oad
Dark Elf Necromancer - Fara's Hole in the Wall, Sadrith Mora
Orc warrior - Ghorak Manor, Caldera
Orc archer - Ghorak Manor, Caldera
Dark Elf archer - Khuul Trade House
Imperial knight - Ald Velothi Trade Houset
Imperial warrior - Fort Darius
Redoran Patron - Ald Ruhn, Skaar, Redoran Council Hall
Paladin - Wolverine Hall, Imperial Shrine
Breton Theif - House of Earthly Delights, Suran