Two things come to me right off.
1. When selecting what to build (in the city) next, always go for buildings that provide
. Unless there is an immediate and dire need for something else,
takes priority as the more you have, the faster everything else will get built. Food can wait, especially in the very early part of the game, since there are no really good sources early game.
1a. Well, the bit about
is partly wrong. There is a good source. It is called Animals. You have to hunt animals to develop properly in the early game.
2. When sending units out to hunt or to explore, which are basically the same thing, you should send out stacks. That is, have a Warrior, a Scout, and a Healer (Wise Woman) at the least, in the same square all times. Once you get Hunter type units, it can be a good idea to include one of those. You can also double-click on the square to select all units in that square (except for cities, as double clicking them will open the city screen) so you can move them all at once.
2a. When exploring or hunting, never pass up entering a square with huts on it. In the video in your 2nd post, your unit heading North passed one up. It was probably because you had "show yields" on and just did not see it. The second such hut they came across provided the free Wise Woman unit.
I've only gotten about half way through the video in the 2nd post so far, as it is very frustrating for me personally to see someone stumbling over things that seem obvious to me. I do realize that you have not played the game before and are just learning though, so I'm trying to refrain from being overly critical. Let me know if I fail, as I do that sometimes.
Something to keep in mind though. Despite having a lot more experience than you do, I also often find myself a bit behind the AI during the early and mid Prehistoric Era. Don't worry too much about it. You should be able to do well enough, unless you set the difficulty to Immortal or something silly like that.
Actually, I can think of something you may have done wrong during setup. You failed to reduce the default number of AI players. Personally, I always reduce the number of AI players to about half of as many as the game defaults to (based on map size). However, this is a personal preference as I like to have more room to expand (and hunt) into, so it may or may not count as an error. Also, having more AI means your computer has more work to do each turn which slows down the game and makes for larger savegame sizes.
Except this: Rejoice in the not knowing. It gives you the blessed opportunity to make the discoveries that can make this game so much fun.
