I am not an expert but I own a tube integreted amp that will run different types of tubes. Currently I own KT88 and KT77 tube sets and the two sound very different when run so yes, different tubes in different monoblocks should sound very different when played together.

Even though the amps have been "refurbished" beings the tubes differ, as you described, there will certainly be a variation in sound. Even though the tubes were tested and are functioning the output will vary due to age, brand,etc.
What you should do is retube both amps with new, matching tubes. It would be even better if you can get tubes whose parameters (i.e., gain, transconductance, plate & load resistance, etc) match so as to have, as close as possible, identical amps. Also, if the power supply output in each amp varies somewhat this, too, can affect how each amp sounds. Taking things to an extreme; if the specs of other components (caps, resitors, pots, coils) in these amps vary enough this will also alter the sound.
But first I would start by replacing all the tubes. From my experience this will make both amps sound the same.

You will have to begin with two amps that are identical to each other which means tubes that are "working" could still not be working in identical fashion. Tubes and other components age and this affects their performance even though they measure as "OK". Capacitors and resistiors drift away from their intial values - and EICO as a budget oriented product line did not hold tight tolerances on their components when they were built - and these variances could affect sound quality to some extent. Not typically to the point where EQ is required to bring the amplifier into line but the amps could be dissimilar despite being refurbished.

However, the questions you ask will get various answers from different people familiar with tube amplifiers. As with many things audio, some people consider all tubes that meet the basic specifications of a 12AX7 or EL34 to be essentially equivalent products which can be interchanged without upsetting the apple cart. Others will tell you all tubes, even from the same manufacturer and the same type of tube, will have different characteristics which will affect the final sound of the amplifier. For most people the truth will be found somewhere in between those two opinions.

I would spend the money to buy new tubes for both amps to get each side matching the other. Be aware this still might not insure absolute matching between your speakers for several reasons. First, if other components within the amplifiers are not similar due to time differences in actual production and changes made to the amplifiers over time or due to past repairs there could easily be dissimilar sounds from each amplifier. If a tech feels tubes are similar if they are measure OK, then that same tech probably feels two amplifiers with the same model number should sound the same or two capacitors/resistors should sound the same. Depending on how keen you are to the sound of the amplifiers, this might or might not be true, with the age of your amplifiers there are very likely distinct differences between the two amplifiers even if they test alike.

However, the most common probable cause of a channel to channel difference is one you appear to have overlooked. The two speakers do not presently occupy the same space and therefore will have very different sound from side to side due to interaction with the room and their surroundings. Here's what I would suggest before you do anything else, pull both speakers out into the center of the room and place them side by side. Disconnect your EQ and run both amplifiers to the respective speaker without any tone controls or other signal contouring devices applied. If you have the ability to listen in mono rather than stereo, this would be beneficial to making accurate judgements about channel to channel or amp to amp sound quality - many audio manufacturers listen to their products with a mono source to ensure piece to piece stability of sound quality. Listen to the speakers in this position with a variety of music sources to determine just how much difference there is between amplifiers and how much of the difference you were hearing was due to their placement in the room. Remember speakers also vary somewhat from piece to piece and even when placed side by side your two speakers might not be exactly identical in sound qaulity either. If you are still aware of a large disparity between channels, swap the amplifiers between speakers, connect right channel amp to left channel speaker and vice versa. Give another listen to determine what the amps are doing. From there you should have a basis for how to proceed.

When you reconnect your system, try it without the EQ in line.

Various tubes often do have a particular sound characteristic. Before addressing
tube characteristics, I'd jet on down to Radio Shack and buy an inexpensive SPL meter.
You should be able to find one for 30 bucks or so. Level match the amps and mark the
balance point for a reference.

I don't disagree with any of what has been suggested by the previous posters, but I'd
personally bias the output tubes to ensure they are also of equal value before determining
sound preferences and spending money on the tubes I might prefer.

If your speakers allow for bi-amping, you might even want to run the tweeters off of one
amp and the bass drivers off the other...if you happen to feel one is better suited in
that area.