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.
could there be a blob of liquid water in space the size of, say, a planet?
It's pretty unlikely, but yes, theoretically it's possible.
Could the water being ejected by that black hole ever condense into something of the size I'm describing?
That would be one of the very few scenarios where something like this could form. Maybe. It depends on the density fluctuations of the water ejecta. You need a condensation center to gather a large mass of water and get the planet started.
Would it boil over immediately?
A cloud of stuff contracting under its own gravity will definitely heat up. But here's the thing - it does not matter whether the water is solid, liquid or gas. It would collapse just the same. Gravity is stronger. Doesn't matter whether is cold as ice, or boiling like crazy.
Once it's a small sphere of water in some form, more complex phenomena will take over. See below.
Would the elements near the middle heat up and maybe fuse?
Maybe some heat will be provided by the initial collapse. Maybe it does have some radioactive impurities which will heat it up. But anyway, over a very long time it would tend to cool down.
In general, the core would be an exotic form of high-pressure ice, no matter what the temperature - water is solid at very high pressure, even if you elevate the temp a lot. Above that there will be a layer of liquid water, if the whole planet has enough warmth, or just plain old ice if it's too cold altogether. The surface might be solid again, cold ice (if the planet is wandering alone in space), or liquid (if it's close to a star). There may be a water atmosphere above, either wispy and thin (cold planet) or thick (warm planet).
http://www.lsbu.ac.uk/water/phase.html
Roughly how large a body of water could you have that's stable given that it could be protected from the vacuum?
When the escape velocity of water molecules is bigger than the average thermal speed, the body is stable. In other words: Warm planet - needs to be bigger to keep the water in. Cold planet - it can be smaller.
A small chunk of ice could survive for quite some time in outer space before sublimating to nothing. A Moon-size blob of ice would probably be stable forever. But if there's warm water on the surface, and a thick water atmosphere, it would probably require an Earth-like mass (and gravity) to keep the water from escaping.
And just for fun, supposing the body of water was "bootstrapped" with primitive life or the ingredients for it, could it potentially support life?
If it's life that doesn't need dry land and ocean bottom to survive, then yes.
There's a type of exoplanet that is similar to what you describe. Not identical, but kind of close:
http://en.wikipedia.org/wiki/Ocean_planet
Best Answer
I'm very far from an expert, but it's an interesting question and I have a few thoughts.
Regarding the first question, "could a water world be stable for thousands of years with most of its surface remaining covered in water", being somewhat pedantic the Earth would meet this description, so yes (and I presume you really mean 'millions' if not 'billions' of years?) - although even then the "Snowball Earth" hypothesis would suggest that this state is not completely stable on those timescales. There is presumably a relatively narrow window of temperatures for stability, as too cold and the water will freeze to ice (e.g. the assorted ice-rich moons of the outer Solar System), while too hot and you'll lack a defined surface as water transitions to vapour. Both would appear to be runaway endpoints, i.e. as the planet heats up, the atmospheric water content increases, which increases the greenhouse effect, which promotes heating, etc.
Gravity might also be problematic, at low mass the atmosphere will be less dense and more easily lost, while at higher gravities the efficacy of water vapour as a greenhouse gas might lead to high temperatures and pressures. Which I guess is some kind of consideration for your second question.
I don't quite follow the tidal locking question, but this would suggest a reasonably compact orbit which would in turn lead to the temperature runaway and/or loss of atmosphere problem (and literal evaporation if there's no rock core). Maybe with a cool M-dwarf star this might be possible, I don't know.
A quick browse of the arXiv turned up an interesting looking paper from the journal Icarus
http://arxiv.org/abs/astro-ph/0308324
which might give some more insight (from someone who knows what they're talking about ;) but i've not yet had time to give it a read-through - skipping to the conclusions suggests that it is at least possible, if an ice-rich planet subsequently migrates inwards.