As it takes the sun about 250 million years (250 My) to orbit the galaxy, the proper motion of stars relative to the Sun will be the dominant effect of changes in the sky. The visible effects of the rotation will be far slower.
All stars move in the sky, some faster some slower, and in more or less random directions, not just moving around the galaxy. For example, Vega moves about 1 degree every 11,000 years. Around 12,000 BCE it was the pole star, and will be so again around 14,000 CE. Between now and then, other stars like Gamma Cephei and Iota Cephei will temporarily take the role of Polaris.
By 250 million years most stars will be far from their current position in the sky, but because of uncertainties it's impossible to say just where they'll be. For example, if the estimate of 250 My is wrong by just 1% (or 2.5 My), that means about 100 periods of Vega. Hence by that time Vega could be anywhere at all even if it stays in our general neighbourhood - which is certainly not guaranteed.
Galaxies move as well, but because they are much further away, their apparent position changes much slower than that of stars. It will be mainly our rotation around the galaxy that moves them in the sky.
Using telescopes we have already seen differences in the positions of the closer stars. In 10,000 years many changes will be visible to the naked eye. By the year 250 My, the sky won't look even remotely like the present.
The early universe was a hot, high-friction environment in which solid objects couldn't form, and even if one had, it would have been kept at rest relative to the Hubble flow because of friction.
Much, much later, stars, solar systems, and other structures began to form by gravitational collapse. There is a kind of scale-invariance in this collapse. What I mean by that is the following. Take a uniform, spherical cloud of gas and dust of radius $r$. Calculate the gravitational acceleration at the edge of the cloud, and from that find the time it takes for the cloud to collapse by some fixed fraction of $r$, say $r/10$. This time turns out not to depend on $r$. Because of this, all the different levels of the hierarchical structure of the universe formed more or less at the same time -- it wasn't top-down or bottom-up.
In such a collapse, the matter accelerates due to gravity, and by conservation of energy the final speeds depend on the final size of the system like $r^{-1/2}$. Therefore if you want to see very rapidly moving objects, you want to look at things that have collapsed to very small sizes, such as neutron stars or matter falling into or orbiting around black holes. These objects have motion at speeds comparable to the speed of light.
Because of scale-invariance, this argument about $v\propto r^{-1/2}$ is basically not coupled at all to cosmological structure.
Also, do relative speeds get very high if we correct out the part due to universe expansion ?
This is a little subtle, but really we can't correct out this effect -- we can't even define what it is. That is, general relativity doesn't provide any well defined, unique way of describing the motion of one object from another object far away. You may hear people talking about the speed at which cosmologically distant galaxies are receding from us, but that's either (a) sloppy popularizations, or (b) people who have in mind a particular and somewhat arbitrary definition. The arbitrary definition is that you place a chain of rulers stretching from object A to cosmologically distant object B, and let each ruler be at rest relative to the cosmic microwave background. If you do use this definition, there are objects that we can observe and that are receding from us faster than the speed of light (Davis 2004), which should make it clear that this definition doesn't mean anything dynamically.
where is the energy going?
Energy isn't conserved in cosmology: Total energy of the Universe
Davis and Lineweaver, Publications of the Astronomical Society of Australia, 21 (2004) 97, msowww.anu.edu.au/~charley/papers/DavisLineweaver04.pdf
Best Answer
Velocity does indeed have to be measured relative to something. We can measure our radial velocity relative to any other astronomical object we care to, by measuring Doppler shifts. But if you want to know our velocity "relative to the Universe as a whole" rather than relative to any one object, we have to be a bit careful to define our terms.
Because the Universe appears to be approximately homogeneous and isotropic, it makes sense to define a "rest frame" at any given point. (The rest frames at different points are moving with respect to each other -- that's what it means to say that the Universe is expanding.) This "rest frame" is essentially the frame in which the stuff surrounding that point appears to be moving isotropically (the same in all directions). In practice, the best way to define that rest frame is to find the frame in which the cosmic microwave background appears the same in all directions (has no dipole moment, to be precise). Relative to this frame, the local group of galaxies is moving at about 600 km/s (Wikipedia gives precise numbers and probably citations that I'm too lazy to look up).
People sometimes worry about whether the existence of a preferred "rest frame" of this sort is in conflict with the principle of relativity. The answer is that it isn't. There are a couple of ways to see why. One is to note that the principle of relativity says that the laws of physics have no preferred frames, but particular solutions to the laws can have preferred frames. Another way of putting it, which I prefer, is that the "rest frame" we use in cosmology is simply the center-of-momentum frame of a bunch of particles (namely the CMB photons in our neighborhood). In other contexts, we're not surprised or worried by the fact that a bunch of particles have a rest frame, so why should we worry about it here?