Solution:

Call a city "even" or "odd" according to whether the number of paved roads coming out of it is even or odd. Note the following.

Lemma: No matter which roads are paved, there will be an even (possibly zero) number of even cities.

To see why this is true, let $d_{i}$ be the number of paved roads leading out of city $i$. The sum
$$d_{1}+d_{2}+\cdots+d_{1000}$$
counts each paved road exactly twice, and hence will be an even number (this is known as the "Handshake Lemma"). If there were an odd number of even cities, then there would be an odd number of odd cities (since there are 1000 cities and 1000 is even). But then the sum above would be odd, a contradiction.

Using this lemma, we can create an algorithm which will eventually pave the roads so that all cities are odd.

1. Start by paving all the roads. If each city is odd, we are done.

2. Otherwise, find an even city $x$. By the lemma, there will be at least one other even city, $y$. Consider the path joining $x$ and $y$. Change the "state" of all the roads in this path (in other words, if a road is paved, unpave it; if it is dirt, pave it). This procedure changes the parity of $x$ and $y$ (i.e., changes them from even to odd), but does not alter the parity of any other city in Euleria, because if $z$ is a city on the path from $x$ to $y$, both the road going into $z$ (from the $x$-direction) and the road leaving it (heading towards $y$) will have changed.

3. Step 2 thus reduces the number of even cities by 2. Repeat this step as much as needed until the number of even cities is zero.

Solution:

We will think of Euleria as a connected graph (a network of vertices joined by edges), where each city is a vertex and each dirt road joining two cities is an edge. Number the vertices $1,2, \ldots, 1000$. For each $i=1,2, \ldots, 500$, consider any path from vertex $2i-1$ to vertex $2i$ (we know such a path exists, since the graph is connected), and place a mark on each edge used in the path. Then pave all the roads (edges) that have an odd number of marks. To show that this scheme meets the requirements, it is enough to prove that, for each vertex $v$, the edges incident to it have an odd total number of marks, since the number of such edges with an odd number of marks will then be odd. But consider all the occurrences of $v$ in any of our 500 paths. Notice that $v$ is an endpoint of one such path, which therefore contributes one mark on an edge incident to $v$; any other occurrence of $v$ is internal to a path, which therefore contributes two marks, one on the edge leading into $v$ and another on the edge leading out of it. It follows that the total number of marks on edges incident to $v$ is odd. This completes the proof.