There is a worker in twist mountain who gives you 1st, 3rd, and 4th gen fossils (kabuto, omanyte, anorith, lilleep, crainidos, and sheildon). He gives you a random fossil (excluding 5th gen fossils) daily so you can come back everyday to get another. This guy will only give you them after you defeat the elite four so if you didnt do that you'll have to wait
For the fifth gen fossils, you get them near the entrance of relic castle on the first floor past the quicksand to the left of the entrance. A backpacker will give you the fossil (archen/tirtuga) but only one can be chosen.