First, the fact that an object at rest has energy $mc^2$ is a simple matter of dimensional analysis. If you accept that energy and mass are related, and you know that nature has a natural velocity $c$, then $E=mc^2$ is the simplest thing you can write that describes this. The only complication could have been some numerical factor in front of $m$.
Now, the statement about traveling through time 'at the speed of light' needs to be qualified. You can easily see that it does not make sense if you use ordinary definitions: the speed of light is measured in 'length per time', while a 'speed through time' would be measured by 'time per time', which is just a number.
However, we can make sense of this statement. We think of an observer as tracing a path through spacetime. To denote a point on this path we use a single coordinate that we call $\tau$. The path is defined by the functions $t(\tau)$ and $x(\tau)$: for each value of $\tau$ the observer is at a specific place $x$ at a specific time $t$.
Note that so far $\tau$ is not time: it just just a fictitious coordinate that we use to denote points on the path. I did not even have to specify what units we measure it in.
Let's say we measure $\tau$ in seconds. We can now define a 'velocity vector' $u$ through spacetime, which is the rate at which $t$ and $x$ change when we change $\tau$:
$$u=\left(c \frac{dt}{d\tau},\frac{dx}{d\tau}\right).$$ Notice that I snuck a $c$ in there, to make sure $u$ has units of velocity.
The first component of $u$ is a nice definition of our velocity through time. The second component is some way of measuring velocity through space, but it is not the same as the velocity we usually think about, which is $\frac{dx}{dt}$.
Now comes a very nice mathematical theorem, which says that we can always assign values of $\tau$ to points on the path such that $|u(\tau)|=c$ at each point. With this choice of $\tau$, our 'velocity' $u$ is a constant, equal to the speed of light: no matter if we still or move very fast, our velocity through spacetime is the same. If we are sitting still, it just means that we are 'moving faster' in the time direction. If we are moving very fast (by the usual definition of moving...), then our velocity in the time direction will be smaller to compensate. Our only choice is where to point our velocity: a bit more in the time direction, or a bit more in the space direction.
I think this is a very beautiful picture, but it is also a bit misleading. Because $\tau$ is a fictitious coordinate, there are many choices for it and they are all equally good. We could just as well have chosen $|u(\tau)|=2c$, or $|u(\tau)|$ not even constant. So bear in mind that this is all a matter of convention.