Another important point is that one should never try to move around in INSERT mode. If you do, you're limiting yourself to moving around with the arrow keys and also are grouping multiple edits that you may want to undo piece by piece with u. If you need to move around, change to NORMAL mode and then move.
Yes, it's normal to hit Escape a lot. Personally, I like to have CapsLock act as Escape with `setxkbmap -option caps:escape`. If I ever really want to write something in all caps, it's always seemed faster to hold Shift with my left pinky.
> It's like learning to touch type all over again.
A very apt way to put it. Touch typing is like learning a language for your fingers. You do it once for your language (e.g. English), and now you're doing it for vi NORMAL mode, which is basically a language for text editing and navigation.
Like TeMPOraL said though, if you feel the frustration getting to you, you can just relax however much you want, and take things at the pace most comfortable to you.
Muscle memory does take time to build up, but it goes much faster if you don't try to take on too much at the same time. Just focus on small pieces at a time. Spend 30 minutes fully focused on basic semantic navigation (forward/backward by letter, word, paragraph, expression; up/down by line, page). Spend another 30 minutes on navigating via incremental search (an extremely useful trick, it can easily replace half of your navigation). Etc.
(This is my tried&true method I used to master various tricks in Emacs.)
Also relax, and notice that half your frustration comes from the fact that you already know another set of conventions, and it's tempting to just stick to it. But the new one will get easier very quickly :).
I'm learning right now - as in, I started on Sunday. It's not hard to learn, but it's hard to use effectively. I could edit code twice as fast if I reverted to my standard keybindings, but I'm waiting for muscle memory to build.
Learning isn't hard, but building muscle memory is a tonne of work. It's like learning to touch type all over again.