Low fps issues for character movement

I have this CharacterMovement.cs script which works great for moving around my character except for in the cases of the frame rate being low. What happens is that when walking of e.g. a cliff the character does not just fall but also instead moves up and down in an irregular motion - and can even end up at a higher point than the cliff the character walked of. With decent framerates everything works perfectly.

If I had missed a *deltatime somewhere this would generally make physics behave slower on low end devices but in this case the gravity just becomes weird in a very irregular way.

Can anyone pinpoint the culprit?

 using UnityEngine;
 using System.Collections;
 
 /// <summary>
 /// This takes care of moving and animating a character. Can be plugged in with multiple different input methods.
 /// </summary>
 public class CharacterMovement : MonoBehaviour
 {
     [SerializeField] private float runSpeed = 5.0f;
 
     // How high do we jump when pressing jump
     [SerializeField] private float jumpHeight = 2f;
     [SerializeField] private float inAirControlAcceleration = 3.0f;
 
     [SerializeField] private float speedSmoothing = 10.0f;
     [SerializeField] private float rotateSpeed = 1000.0f;
 
     private CharacterController CharacterController;
     private CharacterState PlayerState;
     protected IInputMethod CurrentInput;
 
     // The gravity for the character
     private const float Gravity = 9.8f;
   
     private Vector3 InAirVelocity = Vector3.zero;
 
     // The current move direction in x-z
     private Vector3 MoveDirection = Vector3.zero;
     // The current vertical speed
     private float VerticalSpeed;
     // The current x-z move speed
     private float MoveSpeed;
     private float TargetSpeed;
 
     // The last collision flags returned from controller.Move
     private CollisionFlags CollisionFlags;
 
     private const float GroundedTimeout = 0.25f;
     private float LastGroundedTime = 0.0f;
 
     private const float MovementDistanceThreshold = 0.5f;
     // The coordinates which the player will walk towards
     private Vector3 TargetPosition;
 
     public bool isControllable = true;
 
     protected void Awake()
     {
         CharacterController = GetComponent<CharacterController>();
 
         MoveDirection = transform.forward;
         TargetPosition = transform.position;
     }
 
     private Vector3 GetInputDirection()
     {
         TargetPosition = CurrentInput.GetMoveTarget();
         if (TargetPosition != Vector3.zero)
         {
             Vector3 newDirection = TargetPosition - transform.position;
             newDirection.y = 0;
 
             if (newDirection.magnitude <= MovementDistanceThreshold)
             {
                 // This is to ensure that the controller actually reaches it goal
                 //Debug.Log("Reached movement target");
                 newDirection = Vector3.zero;
             }
 
             return newDirection.normalized;
         }
         return Vector3.zero;
     }
 
     private void UpdateSmoothedMovementDirection()
     {
         // Target direction relative to the camera
         Vector3 targetDirection = GetInputDirection();
 
         // Grounded controls
         if (IsGroundedWithTimeout())
         {
             /* if (isMoving != wasMoving)
                     lockCameraTimer = 0.0f;*/
 
             // Choose target speed
             TargetSpeed = 0f;
 
             // We store speed and direction seperately,
             // so that when the character stands still we still have a valid forward direction
             // moveDirection is always normalized, and we only update it if there is user input.
             if (targetDirection != Vector3.zero)
             {
                 MoveDirection = Vector3.RotateTowards(MoveDirection, targetDirection, rotateSpeed * Mathf.Deg2Rad * Time.deltaTime, 0f);
                 MoveDirection = MoveDirection.normalized;
 
                 PlayerState = CharacterState.Running;
                 TargetSpeed = runSpeed;
             }
 
             // Smooth the speed based on the current target direction
             float curSmooth = speedSmoothing * Time.deltaTime;
 
             MoveSpeed = Mathf.Lerp(MoveSpeed, TargetSpeed, curSmooth);
 
             if (MoveSpeed < 0.1f)
             {
                 MoveSpeed = 0f;
             }
         }
         else
         {
             // In air controls
             InAirVelocity += targetDirection * Time.deltaTime * inAirControlAcceleration;
         }
     }
 
    
 
     private void CalculateVerticalSpeed()
     {
         if (isControllable) // don't move player at all if not controllable.
         {
             if (IsGroundedWithTimeout() && !Jumping)
             {
                 VerticalSpeed = 0.0f;
             }
             else
             {
                 VerticalSpeed -= Gravity * Time.deltaTime;
                 //VerticalSpeed -= Gravity;
             }
         }
     }
    
 
     private bool GetDirectionValidity()
     {
         // If the character controller registers a collision in the front
         return CollisionFlags != (CollisionFlags) 3 && CollisionFlags != (CollisionFlags) 7;
     }
 
     //private void 
     private void Update()
     {
         if (!isControllable)
         {
             // kill all inputs if not controllable.
             Input.ResetInputAxes();
         }
 
         CurrentInput.Update();
 
         UpdateSmoothedMovementDirection();
 
         CalculateVerticalSpeed();
 
         // Calculate actual motion
         //Debug.Log("Vertical speed is: " + VerticalSpeed);
         //Debug.Log("Inair vel: " + InAirVelocity);
         Vector3 movement = MoveDirection * MoveSpeed + new Vector3(0, VerticalSpeed, 0) + InAirVelocity;
         movement *= Time.deltaTime;
 
         // Move the controller
         CollisionFlags = CharacterController.Move(movement);
 
         if (!GetDirectionValidity())
             TargetPosition = transform.position;
 

         SetRotation(movement);
 
         if (CharacterController.isGrounded)
         {
             LastGroundedTime = Time.time;
             InAirVelocity = Vector3.zero;
             // We are in jump mode but just became grounded
             if (Jumping)
             {
                 Jumping = false;
                 PlayerState = CharacterState.Idle;
             }
         }
     }
 
     // Set rotation to the move direction
     private void SetRotation(Vector3 movement)
     {
         if (CharacterController.isGrounded)
         {
             transform.rotation = Quaternion.LookRotation(MoveDirection);
         }
         else
         {
             Vector3 xzMove = movement;
             xzMove.y = 0;
             if (xzMove.sqrMagnitude > 0.001f)
             {
                 transform.rotation = Quaternion.LookRotation(xzMove);
             }
         }
     }
 
    
     //The unity Charactercontroller is bugged and constantly toggles between isgrounded false/true
     //This fixes it
     private bool IsGroundedWithTimeout()
     {
         return LastGroundedTime + GroundedTimeout > Time.time;
     }
 }