Why is a fire service considered to be a non-rival service, while a highway is considered to be a rival good? We consider highways to be an example of an impure private good because while it is non-excludable, it is a rival good. That is, another person's consumption (usage) of the highway affects my usage of it. 

In that same sense, wouldn't a fire station also be rival, at least in theory?

For example, if a fire stations has five trucks for a locality, and 6 fires break out at separate places, why can't we consider this service as a rival service?
One common definition of a non-rival good (see here and (A)) is a good for which the consumption of additional units involves zero marginal social costs of production. On this definition the service provided by a fire service would always be rival, because (even with plenty of capacity in terms of fire engines and staff) each visit to attend a fire involves some extra cost (eg vehicle fuel).

More loosely, a good may be said to be rival if consumption by one person prevents simultaneous consumption by others (this can also be found here), implying that a good is non-rival where that is not the case.  In this looser sense, infrastructure such as highways and services such as the fire service might be held to be non-rival in circumstances where capacity is large enough that consumption by some rarely prevents or interferes with consumption by others.

For those who adopt this looser definition, the difference between a highway network and a fire service, which may lead to the former but not the latter being characterised as a rival good, relates I think to the likely level of supply or capacity.  Given high levels of vehicle use with peaks at certain times (rush hours), and given the costs of road-building and other demands on land use, it isn't likely to be practicable to provide enough highways in the right places to make traffic jams a rarity.  On the other hand, given that a fire at any one location is a rare event, and given normally a high degree of independence between fires at different locations, it should be possible to provide sufficient capacity in a fire service that the scenario of fewer fire engines than fires will rarely occur.

Reference

(A) Nicholson W (9th edn 2005)  Microeconomic Theory: Basic principles &amp; Extensions p 596.