parallel port routing
OK, if I guess correctly that your supply plane is continuous and well decoupled to the ground plane, then traces on either side will be the same height above an effective signal return plane.  If I guess correctly that your PCB thickness is 1.6 mm and I'm reading the correct column on the International Circuits Web page that you pointed to, then that height is 9 mils.  If I guess correctly that your traces are 6 mils wide in 1 ounce copper and the PCB material is FR4 with a dielectric constant of 4.5, then I calculate the characteristic impedance of your traces to be about 82 ohms and the propagation delay to be 0.152 ns per inch.  This all looks fine, so it wouldn't matter much if my guesses were a bit wrong.

So, your data, address and chip select signals are flying around at over six inches per nanosecond and unless you're operating right on the edge there should be plenty of time for any ringing to settle out, so don't worry about how these signals are routed.  You said that the clock rate is 18 MHz (55.5 ns period) and that the access time is 55 ns.  I assume that's not what you meant.  The cycle time will be 55.5 ns, but you can't use memory devices with a 55 ns access time to cycle at 55.5 ns because you've almost no margin.

If the memories have a clock signal, then you have to consider more than just whether the logic level settles down in time, you have to worry about the integrity of the clock edge.  Ideally, you want the edges to propagate cleanly along the trace and for there to be no reflection at the end of the trace.  (What you don't want is a reflection that causes the edge to teeter back and forth over the logic threshold.)  The best way to get this is to run the trace without branches, as in your second diagram, and to terminate the trace at its end with something close to its characteristic impedance.  For example, you could have two 165 ohm resistors, one to supply and one to ground.  Obviously, make sure that the drive circuit is OK with this.  You may get away without the termination, but you're asking the question so I assume you want to make sure it's right.

Summary: Route asynchronous signals (data, address, chip select, etc.) however you want.  Route clocks point-to-point without branches and terminate at the far end with the characteristic impedance to kill reflections.