Ciao!
Il relè è in realtà una scheda con due relè. Questa, per la precisione:
http://www.ebay.it/itm/111519865048?ssPageName=STRK:MEWNX:IT&_trksid=p3984.m1497.l2649
quindi, per quanto ho capito, basta collegarla al 5+ e gnd, dargli due pin dall'arduino.
Devo fare delle prove col tester e capire se un secondo è sufficiente, ma credo proprio di si! 
Per quanto riguarda lo Sketch, c'ho rimesso un po' mano seguendo i tuoi ottimi consigli!
(dal codice ho tolto i primi commenti sui pin, altrimenti superavo i 9000 caratteri.Tanto rimangono come prima)
// includere la libreria per il display:
#include <LiquidCrystal.h>
// includere la libreria per la sonda:
#include <MAX6675.h>
#define SO 9 // pin SO del MAX6675 (modificato in 9, era 11)
#define CS 10 // pin CS del MAX6675
#define SCIK 13 // pin SCK del MAX6675
#define units 1 // Unità di misura temp (0 = raw, 1 = ˚C, 2 = ˚F)
int temperatura = 0; // Variabile della temperatura
// Inizializza la libreria del MAX6675
MAX6675 temp(CS,SO,SCIK,units);
/*
Viene creata l'istanza dell'oggetto LiquidCrystal chiamata lcd in cui
sono indicati i pin dell'LCD collegati alle uscite digitali di Arduino
*/
LiquidCrystal lcd(12, 11, 5, 4, 3, 2);
uint8_t degree[8] = {140,146,146,140,128,128,128,128}; // Crea il simbolo dei gradi
#define intervallo 1000 // Intervallo di tempo tra una lettura e l'altra della sonda
unsigned long Millsintervallo = 0; // Memorizza il tempo trascorso dall'ultima volta che la temperatura è stata visualizzata
#define Temp1 45 // Temperatura limite per la marcia 0 (tutto spento)
#define Temp2 55 // Temperatura limite per la marcia 1 (acceso il relè1)
#define Temp3 60 // Temperatura limite per la marcia 2 (acceso il relè2)
#define Temp4 62 // Temperatura limite per la marcia 3 (acceso il relè3)
#define marcia1 6 // Pin collegamento al relè per la 1° marcia
#define marcia2 7 // Pin collegamento al relè per la 2° marcia
#define marcia3 8 // Pin collegamento al relè per la 3° marcia
#define marcia4 14 // Pin collegamento al relè per la 4° marcia
byte marcia = 0; // definisce la marcia da mettere
byte prevmarcia = 0; // definisce la marcia che è impostata
byte cambiamarcia = 0; // definisce se bisogna o meno cambiare marcia
unsigned long millsmarcia = 0; // memorizza il tempo trascorso dall'ultimo cambio della variabile marcia
#define iterMarcia 5000 // Intervallo di tempo che deve durare il cambio marcia
#define temporele 1000 // definisce il tempo che il relè deve aspettare prima di commutare
void setup() {
// mette ad OUTPUT i pin dei 4 relè
pinMode(marcia1, OUTPUT);
pinMode(marcia2, OUTPUT);
pinMode(marcia3, OUTPUT);
pinMode(marcia4, OUTPUT);
// impostare il numero di colonne ed il numero di righe di lcd
lcd.begin(16, 2);
lcd.createChar(0, degree); // Crea il simbolo dei gradi
// Visualizzo sul display la parte fissa del messaggio
lcd.setCursor(0, 0);
lcd.print("Temp: ");
temperatura = temp.read_temp();
if (temperatura < 10)
{
lcd.print("0");
}
lcd.print(temperatura);
lcd.setCursor(7, 0);
lcd.write((byte)0); // Scrive il simbolo dei gradi
lcd.print("C");
lcd.setCursor(0, 1); // Cambia colonna
lcd.print("Marcia: ");
lcd.setCursor(8, 1);
lcd.print(marcia);
}
void loop() {
if (millis() - Millsintervallo > intervallo ) // controlla la temperatura dopo il tempo dichiarato in "intervallo"
{
Millsintervallo = millis(); // Memorizza il valore di mills
// Legge la temperatura dal MAX6675
temperatura = temp.read_temp();
// ***** queste righe non so se vanno qui *****
lcd.setCursor(5, 0);
if (temperatura < 10)
{
lcd.print("0");
}
lcd.print(temperatura);
// ***** fino a qui *****
if (temperatura < Temp1)
{
marcia = 0;
if (marcia != cambiamarcia)
{
millsmarcia = millis();
cambiamarcia = marcia;
}
}
else if (temperatura >= Temp1 and temperatura < Temp2)
{
marcia = 1;
if (marcia != cambiamarcia)
{
millsmarcia = millis();
cambiamarcia = marcia;
}
}
else if (temperatura >= Temp2 and temperatura < Temp3)
{
marcia = 2;
if (marcia != cambiamarcia)
{
millsmarcia = millis();
cambiamarcia = marcia;
}
}
else if (temperatura >= Temp3 and temperatura < Temp4)
{
marcia = 3;
if (marcia != cambiamarcia)
{
millsmarcia = millis();
cambiamarcia = marcia;
}
}
else
{
marcia = 4;
if (marcia != cambiamarcia)
{
millsmarcia = millis();
cambiamarcia = marcia;
}
}
// ***** queste righe sono da togliere, valgono solo come prova *****
// visualizza sul display il tempo dall'ultimo cambio marcia
lcd.setCursor(10, 0);
lcd.print("T ");
// le due sopra servono solo per un fattore estetico:
// se il tempo è maggiore a 10, all'azzeramento della variabile
// millsmarcia, viene comunque visualizzata la seconda cifra del numero precedente
lcd.setCursor(10, 0);
lcd.print("T ");
lcd.print((millis() - millsmarcia)/1000);
lcd.setCursor(10, 1);
// visualizza sul display la marcia da mettere (DM)
lcd.print("DM ");
lcd.print(marcia);
// ***** fino a qui *****
// se è cambiata marcia, e la durata del cambio è maggiore della variabile iterMarcia
if (prevmarcia != marcia and millis() - millsmarcia > iterMarcia)
{
switch (marcia) {
case 0: // Mette tutto a zero
digitalWrite(marcia1, LOW);
digitalWrite(marcia2, LOW);
digitalWrite(marcia3, LOW);
digitalWrite(marcia4, LOW);
break;
case 1: // Accende il relè 01 (e fa una pausa, onde evitare corrente su du relè)
digitalWrite(marcia2, LOW);
digitalWrite(marcia3, LOW);
digitalWrite(marcia4, LOW);
delay (temporele);
digitalWrite(marcia1, HIGH);
break;
case 2: // Accende il relè 02 (e fa una pausa, onde evitare corrente su du relè)
digitalWrite(marcia1, LOW);
digitalWrite(marcia3, LOW);
digitalWrite(marcia4, LOW);
delay (temporele);
digitalWrite(marcia2, HIGH);
break;
case 3: // Accende il relè 03 (e fa una pausa, onde evitare corrente su du relè)
digitalWrite(marcia1, LOW);
digitalWrite(marcia2, LOW);
digitalWrite(marcia4, LOW);
delay (temporele);
digitalWrite(marcia3, HIGH);
break;
case 4: // Accende il relè 04 (e fa una pausa, onde evitare corrente su du relè)
digitalWrite(marcia1, LOW);
digitalWrite(marcia2, LOW);
digitalWrite(marcia3, LOW);
delay (temporele);
digitalWrite(marcia4, HIGH);
break;
}
// fine dello switch case
lcd.setCursor(8, 1);
// visualizza sull'lcd la marcia corrente
lcd.print(marcia);
// assegna la marcia corrente a quella precedente
prevmarcia = marcia;
}
}
// fine dell'if principale
}
Per quanto riguarda la dichiarazione dei pin e delle costanti, ho preso spunto da questa discussione:
http://forum.arduino.cc/index.php?topic=35477.0
Mi sono risparmiato un "long", poiché della temperatura, adesso, prendo solo l'intero, e le due variabile per gestire i mills (a cui ho cambiato nome) le ho messe giustamente come "unsigned".
Il programma, comunque, funziona.
Se ci fosse altro da ottimizzare, sono ben contento di farlo!
Grazie davvero a tutti!
Ciao