1. Put a Panel on your Form, set its BackgroundColor property to the border color you want. Set the Panel's Padding property to the size of the border you want.
2. Paste the TextBox inside the Panel. Set its Dock property to Fill.
You can manipulate the BorderStyle property of both Panel and TextBox to achieve different visual effects.
When you validate (quick sketch):
EmptyTbxBackColor = Color.Red;
foreach (Textbox tbx in MyListOfTextBoxesToBeValidared)
{
if(tbx.Text == String.Empty) tbx.Parent.BackColor = EmptyTbxBackColor;
}