Is this a full-duplex or half-duplex device? Can you control request-to-send and monitor clear-to-send on both ends of the serial line? Is the serial line point-to-point (like RS-232) or multi-drop (like RS-485)? It will make a (albeit small) difference if you are going to interfere with other already connected devices while negotiating with a newly connected one.
If you think of the handshake process like a modem negotiating a link layer protocol, it uses a standard set of messages to describe the type of communications it would like to have and waits for an "ack" from the other end. In your case I recommend having a "let's talk" standard message that your head end generates with the range of bit rates and waits for the ack from the device.
I also recommend reducing the number of configuration options for the device. Forget about variable data bits, parity bits, and stop bits. The serial communications world is no longer as unstable as it was back in the 70's. Just use 8 data bits, no parity, one stop bit and vary the bit rate. A CRC on the end of messages provides plenty of error-checking.