Ok, so I can't answer my own question, but I can say that I can now talk to my external device over serial, so the speed was not the issue.
For the next person that wants to talk over serial, it would be helpful to know that UTF-8 is NOT the encoding set you need.
Latin1, otherwise known as ISO8859-1 is what you require.
Receiving:
Private NewData As String = BytesToString(Buffer, 0, Buffer.Length, "ISO8859_1")
Sending:
Stream.Write(DataToSend.GetBytes("ISO8859_1"))