There's an error in your statement: you need the domain to be compact, and the range to be connected.
Easy counterexample: restrict the exponential map $\mathbb{R} \rightarrow S^1$ to some interval like (0, 1.5) so that the fibers have different cardinalities.
The definition of proper you quote is not the standard definition, and it is not strong enough to imply this result. Consider the following example: Let $G = S^1$ act on $M = \mathbb{R}^2\smallsetminus\{(0,0)\}$ in the usual way, i.e. by rotations about the origin. This action is clearly free. However, equip $G$ with the discrete topology. Note that this makes the topology on $G$ finer, so the action map $G\times M\to M$ is still continuous (the preimages of open sets were open using the usually topology on $G$, so by making the topology strictly finer, they are still open).
Now, I claim that this action satisfies the definition of proper you state in the first quote. Pick $x$, and then the orbit of $x$ is the circle about the origin of radius $\|x\|$. Pick $y$ not in the orbit of $x$ (so $\|x\|\neq\|y\|$), let $\epsilon = |\|x\| - \|y \||$, and let $V$ and $W$ be the $\epsilon/2$ balls about $x$ and $y$, respectively. It is easy to see that $gV\cap W = \emptyset$ for each $g \in G$, as $gV$ is contained in the "$\epsilon/2$-annulus" about the orbit of $x$, while $W$ doesn't intersect this annulus.
However, obviously, there is no open neighborhood $U$ of any $x$ such that the $gU$ are pairwise disjoint. In fact, for each $x\in M$, any open neighborhood $U$ of $x$ intersects the orbit $Gx$ at infinitely many points.
I'll also mention that the quoted definition of proper doesn't imply many of the other important consequences of proper actions. Proper actions of discrete groups (by the standard definition) have finite stabilizers. But consider the example of $\mathbb{Z}$ acting trivially on a point; it satisfies the quoted definition vacuously (only one orbit), but the stabilizer of the point is $\mathbb{Z}$. Similarly, proper actions by the usual definition have Hausdorff quotients (distinct orbits can be separated by open sets)--in my opinion, this is the the main reason for restricting to proper actions (at least for many purposes). However, the example here satisfies the quoted definition, but the orbits of $(1,0)$ and $(0,1)$ contain arbitrarily close points, as explained at that page.
I'm not familiar with the book you are using, but it sounds like they intended the standard definition: the map $G\times M \to M\times M$ given by $(g,x)\mapsto (x,gx)$ is a proper map, i.e. a closed map such that the preimage of each compact set is compact. tom Dieck's Transformation Groups gives a pretty nice treatment of this definition and its consequences in a general setting starting on page 27.
Best Answer
I think both of the examples given at mathoverflow are actually covering maps.
I claimed in the comments that I had a somewhat discrete example but I transformed it to a manifold-based example. The space $X$ is the Möbius strip and $G = ℤ$. I haven't found a really nice way of describing the action but I'll do what I can.
We start by describing a free action of $ℝ$ on $X$. The quotient is $[0,1[$ and the fibers of the quotient $X↠[0,1[$ are shown on the drawing below.
Notice that the "cut" chosen above to draw the Möbius strip above is special. If we displace the cut, we see an angle appear in the fibers. Below are other drawings of two of the fibers. The one in red is the fiber above $0 ∈ [0,1[$.
The action of $ℝ$ is done by "following the fibers" in a chosen direction, but you need to slow down more and more as you approach the angle of the red line. Maybe it's a bit hard to see that it works on the drawings I gave. Here is a different way of drawing the Möbius strip and the two fibers. Imagine it has an infinite height.
On this drawing, the action of $ℝ$ is isometric on the fibers and easier to see (translate along the $y$ direction and teleport to the other side of the red line when you end up out of the drawing).
To get an action of a discrete group and discrete orbits, we restrict the above action to $ℤ⊆ℝ$. The quotient becomes $[0,1[ × S^1$ and the quotient map is not a covering above $(0,x)$ for any $x ∈ S^1$.
To give you an idea of the initial "discrete" example I had, here is a drawing of it. I don't explain more, it's very similar to what I said above. I built by trying to contradict the properness of the action in the simplest way possible.