( developed for SP2013 on-prem, Nintex forms 2.10 )

This code was inspired by nmarples whose amazing blog post can be found here. He lifts the curtain on the Nintex rules engine and shows the power of combining Javascript with rules, providing clues to this realtime validation concept.

You can implement this solution right away on any form control without any additional configuration, cut and paste as shown below using these 4 simple steps;

1) make sure each form field control is named and the label is associated with the control:

2) paste this CSS in the form's Custom CSS setting:

3) paste this Javascript in the form's Custom JavaScript setting:

lpForm = {

 Validate: function( formControlCall, sourceContext, required, isValid ) {
  // Obtain the internal element input name.
  var formControlID = formControlCall.split( "'" )p1] || "";
  var internalElement = sourceContext.find( "tname^='ctl']nformcontrolid='" + formControlID + "']" );
  // During initial load, people control is a placeholder, no internalElement exists yet, so bail, validation will succeed later
  if ( internalElement.length == 0 ) return;
  var internalElement_name = internalElement.attr( 'name' );
  // Scrub the name.

  var intext = internalElement_name;
  var outtext = intext.split( '$' ).join( '_' );
  // Obtain the label associated for-name of internal element.
  var labelBorder = NWF$( "afor^='" + outtext + "']" )
    .closest( '.nf-filler-control-border' )
    .parent();
  // Required missing.
  if( required && isValid ) labelBorder
    .addClass( 'lp-border-red' ).removeClass( 'lp-border-yell' ).removeClass( 'lp-border-grn' );
  // Optional missing.
  if( !required && isValid ) labelBorder
    .addClass( 'lp-border-yell' ).removeClass( 'lp-border-red' ).removeClass( 'lp-border-grn' );
  // Not missing.
  if( !isValid ) labelBorder
    .addClass( 'lp-border-grn' ).removeClass( 'lp-border-yell' ).removeClass( 'lp-border-red' );
  return isValid;
 },
};

4) paste this expression into a new rule for each form field you wish to validate

( function( formControlCall, isValid ) { lpForm.Validate( formControlCall, sourceContext, true, isValid ) }( "{Control:Self}", {Control:Self} == '' ) );

optional : inside the expression, change true to false to change the field from required to optional

note : in the Condition window {Control:Self} will format itself to appear as {Self} once saved 

Done - Enjoy!

TL;DR Explanation

The above code is a prototype created in an afternoon. There are probably some edge cases that may require additional coding, but this appears to be suitable for all basic form controls.

The 3 important concepts from nmarples that he shares in his blog post are:

• The Rule's Condition expression is evaluated as Javascript. ( This means you can point to any Javascript function in the Condition window and it will be executed )
• You can pass to your function, both, a reference to the current control as a string parameter

  "{Control:Self}"

  and pass the resulting expression as a boolean parameter

  {Control:Self} == ''

  Nintex Runtime Functions this expression is the same as isNullOrEmpty({Control:Self})
• During the OnChange event the function and parameters be executed in an IIFE ( what's an IIFE? Google it, it's useful… )

CSS

3 classes are used to set the associated control back-grounds to red, yellow or green.

Form JavaScript

lpForm : creates a unique namespace where I can safely use any name for my function.

Validate : takes 4 parameters.

formControlCall : a reference to the currently active control
sourceContext : a reference to the context of the DOM
required : true or false ( whether this form field is required or optional )
isValid : true or false ( the result of the provided validation expression - already evaluated )

The process of the function

1. Navigate the DOM to locate the current control's internal element name, it usually looks like: 

   ctl00$PlaceHolderMain$formFiller$FormView$ctl26$ctl16$ac5d43fc_51e7_4d06_b3e8_150731c4bac9

2. Scrub this name to replace "$" with underscores.
3. Use the name to locate the associated label control - the label uses an attribute named for.
4. Locate the parent-border control of the labels.
5. Use .addClass.removeClass to set the label parent-borders to the appropriate CSS class ( background-color )

IIFE

The immediately-invoked function expression gathers the following run-time provided parameters:

a reference to the current control : "{Control:Self}"

and a the validation expression : {Control:Self} == ''

So the IIFE evaluates these two parameters and passes results into the interior function, were all four parameters get passed to the base Validation function.  Then the base function Validation ultimately returns back the isValid boolean, which could be consumed by the Rule too.