Why do electromechanical relay computers tend to use higher voltages?
Historically, the largest use of relays has been associated with the telephone industry.  Before electronic telephone exchanges were introduced in the 1960's, virtually all switching was done using a combination of conventional relays and specialized configurations like crossbar and step-by-step switches.  Relays provided a means to connect two parties directly across a telephone switch with a direct circuit.

In the telephone industry, these relays used 48VDC, which was the standard voltage throughout the exchange.  Initially these were open-frame construction, like this one:



which had the advantage the contacts could be cleaned and adjusted as needed, but they were also subject to dust.  So for industrial use, relays were equipped with dust covers, like this one:



and became available in 6, 12, 24, 48 (AC or DC), and 120/240 AC coil voltages.  Note there are no conventional relays currently available at Digi-Key with either 3.3V or 5V coil voltages.  I am guessing in particular 3.3V is not sufficient to be able to develop enough of a magnetic field to operate this large a relay.

The relay shown above has a 4PDT configuration (or four "Form C" contacts).  This contact arrangement is the same type used in Harry Porter's relay computer (all 415 relays in his computer are the same type).  There is also a 6PDT version available.

Another type of relay is the reed relay, first used in the 1930's.  Once again, it initially was used primarily by the telephone industry.  For example, General Telephone's first electronic switch, #1 EAX introduced in the early 1970's used reed relays to connect the subscribers, controlled by a computer and other logic  built using some of the first TTL integrated circuits.



There are also small general purpose relays that are sealed, but are not reed relays.  They may be either rectangular, or more of a cube in some cases like this one:



All relays available in the 3.3V and 5V coil voltages at Digi-Key appear to be either reed relays or sealed general purpose relays.  However the most complex contact configuration you can get is DPDT.  So it would not be possible to directly replicate Harry Porter's machine using these smaller relays (in many cases, you would have to use two relays in parallel).

Besides coil voltages of 3.3V and 5V, these are also available in several other voltages below 5V and also in 12V and 24V versions.

There are three advantages reed relays and the small sealed GP relays have over conventional ones: they are smaller, they cost much less, and they are faster -- for example a reed relay can often switch in a few hundred microseconds, and a conventional relay may be ten times slower ( a few milliseconds).

You could build a relay computer using reed relays or the small sealed GP relays, and it would certainly be smaller than Harry Porter's, but you wouldn't have the satisfactions of being able to watch the relays operate, and more importantly, hear them operate like you can in his video.  (If you do decided to use conventional relays with a dust cover like the photo above, you may want to check out the surplus market, since those relays cost about $12 apiece new.) 

I'm a little confused about the issue regarding fanout -- all of these relays, both conventional or reed, have contacts that can typically handle either 1A or 2A, so driving twenty other relays would not be an issue.  I'm sure that's plenty.