Bellman-Ford algorithm intuition
I can give you the intuition behind Bellman-Ford.  It is beautiful!  I'm going to do it in an indirect way.  I want to share a warm-up puzzle that might seem unrelated, but stay with me.

Suppose we have a digital door lock with a four-digit code (each digit is 0..9), with a funny property: you can enter in extra stuff between the digits of the code and the lock will still open up.  For instance, if the code was 2749, then you  could enter in 32675049, and the lock would open up, because 32675049 contains 2749 as a subsequence.
Challenge: what is the shortest sequence you can come up with, that will guarantee to open the lock?  You could of course enter in each of the $10^4$ possible codes one by one, but that would require you to enter 40,000 digits; can you find a faster way?

Go ahead, see if you can solve it on your own.
Hint:

 Whatever the secret code is, we need it to appear as a subsequence of your chosen sequence.   If we start with 0123456789, we are guaranteed to get at last one digit into the code.  Can you take it from there?

Hint:

 You should be able to find a sequence of length 40 that suffices.

Really, I want you to solve it yourself!  It'll be rewarding and help you understand Bellman-Ford.

Now back to Bellman-Ford.  Let's consider a graph with no negative cycles, but where edge distances can be positive or negative.  The relax operation has an interesting property:

Suppose the shortest path from $s=v_1$ to
$v_n$ is via the path  $v_1 \to v_2 \to \cdots \to v_{n-1} \to v_n$.  If we do some sequence of relax operations, that includes Relax($v_1,v_2$), Relax($v_2,v_3$), ..., Relax($v_{n-1},v_n$) as a subsequence, then $d[v_n]$ will hold the correct distance from $s$ to $v_n$.

In other words, this refers to a sequence of relax operations where we do some relaxes, then Relax($v_1,v_2$), then relax on some other edges, then Relax($v_2,v_3$), then relax on some more edges, and so on.  The property holds no matter what other relax operations you do in the middle -- you can add as many extra relax operations  in the middle anywhere you want and they won't do any harm.
Moreover, once $d[v_n]$ gets set to the correct value, it stays correct forever.
So if our goal is to come up with the correct distance in $d[v_n]$, we can think of that as a digital door lock   like the one above: there is some secret code (the code is a sequence of edges, namely, $(v_1,v_2),\dots,(v_{n-1},v_n)$) that is not known to us, but if we do a sequence of relax operations on some sequence of edges, and if the secret code appears as a subsequence in there, then the lock will open  (i.e.,, $d[v_n]$ will get set to the correct distance), and will stay open forever after (i.e., $d[v_n]$ will hold the correct value from there on).
So this is just like the digital door lock puzzle above!  The challenge is to construct a sequence of edges, so that if we relax edges in that sequence, it'll surely include the code (the shortest path) as a subsequence.  Now you can verify that the sequence of edge relaxations done by Bellman-Ford exactly matches the solution to the digital door lock puzzle above.
I'll let you prove the property I mentioned above.  It follows from the two lemmas you quoted.