How can voltage actually exist/change if electricity can't actually speed up or slow down?
I've only ever taken those water analogies with a grain of salt. Such analogies are really useful when you first begin to dive into theory, but, at least to me, the actual nature of the electric phenomena is what makes most sense. 

To start, I am sure you have read somewhere that voltage is actually a measure of potential difference between two points, namely ground and some other node (although any two points are still valid, ground is nothing more than an arbitrary reference point in a circuit). Taking it a step further and knowing that:

$$Voltage (V) = \dfrac{Joules}{Coulomb}$$

What we have is an electric field through which we intend to move a charge. If we want to move charge against the field of some charge with the same polarity then we must expend some degree of energy to do so. For instance, if we move one 1 C of charge agaist a field and end up expiring 1 Joule of energy, we say that the potential difference, i.e. voltage, is 1 Volt! 



In example, moving B to A would require some measure of energy in Joules. Depending on the magnitude of the charge you are moving you can calculate the related voltage that move represents. Since A is shown as +Q, then moving from A to B actually releleases energy and B to A requires input (i.e. batteries, for example). 

Now simply take this and naturally extend its the application of voltage in free-space to the application of circuits. The only difference being that the electric field is largely contained within the wires we use to connect devices and circuits. As such, we now note that when a voltage exists across a component that what we really have is a difference in electric field intensity which is characterized by the necessary energy expenditure to move charge across it, voltage. Actually, we initially put energy into the system by chemically generating the voltage to supply a circuit, and then expend that stored energy in the form of EMF, heat, and light depending on your application.

This naturally leads into current, since electric current is nothing more than a derivative of an electric field. Namely, with an electric field exists across a component then a measure of disorder exists. A natural system will always try to minimize this disorder (i.e. entropy). 

As far as your other question goes regarding the "speed of electricity", note that the propagation of the voltage appears instantaneous but the actual speed of electroncs within a wire is really quite slow. See Drift Velocity.