First off I wanted to thank @Eric5h5, @Paulius Liekis and @Herman Tulleken for the answers. I actually used a mixture of solutions.

Basically, I had so much code invested in FixedUpdate, etc. That the pausing solution needed to remain the way it was. Inside my base animation manager class I adjusted the code so that animations run independently of Time.timeScale. I used a spin of Paulius and Herman's methods to achieve this.

This class is a more basic version of what I had to do to get this to work, it involves 2 animations, an in transition and an out transition.

using UnityEngine;
using System.Collections;

[RequireComponent(typeof(Animation))]
public class EQEQAnimationManager : MonoBehaviour 
{
    //for calculating our delta time
    float _timeAtLastFrame = 0F;
    float _timeAtCurrentFrame = 0F;
    float deltaTime = 0F;

    AnimationState _currState;

    bool isPlaying = false;
    float _startTime = 0F;
    float _accumTime = 0F;

    void Update()
    {
        //we create our own deltaTime based on realtimeSinceStartup here
        _timeAtCurrentFrame = Time.realtimeSinceStartup;
        deltaTime = _timeAtCurrentFrame - _timeAtLastFrame;
        _timeAtLastFrame = _timeAtCurrentFrame; 

        if(isPlaying) AnimationUpdate();
     }

     void AnimationUpdate()
     {
        //accumulate time
        _accumTime += deltaTime;
        //normalized time is from 0, the animation's beginning to 1, the end. We'll set it where the accumulated time is in the current animation's duration.
        _currState.normalizedTime = _accumTime/_currState.length; 
        if(_accumTime >= _currState.length) 
        {
            OnAnimationCompleted();
            _currState.enabled = false;
            isPlaying = false;
        }
     }

     public void PlayAnimation(string suffix)
     {
        _accumTime = 0F;
        _currState = animation[gameObject.name + " " + suffix]; //my animations are organized by the name of the game object, and what the animation is (ie "Main Menu Transition In" in which suffix would be "Transition In")
        _currState.weight = 1;
        _currState.blendMode = AnimationBlendMode.Blend;
        _currState.wrapMode = WrapMode.Once;
        _currState.normalizedTime = 0;
        _currState.enabled = true;
        isPlaying = true;
     }

     internal void OnAnimationCompleted()
     {
        //hook for end of animation
     }
 }

In this case, I took advantage of Animation States and AnimationState.normalizedTime, using my custom deltaTime (thanks again Herman) to allow the animation to play as expected even if Time.timeScale is set to 0. Since these are straight-forward, linear animations, I was able to get away with setting the AnimationState's values in PlayAnimation the way I did. In other cases I'd probably want to inject more parameters.

What I also noticed was that I lost connections to my AnimationEvents which I inserted using Unity's Animation Editor. In my case it was a single function call which was fired on completion. Again, because of the linear nature of these animations I was able to get away with just calling that function after the accumulated time reached the length of the animation in my custom update loop.

I hope this helps anyone else with a similar complication. I was lucky that I only had to modify a single class and everything worked as expected. I have good class and package structure to thank for that. :)

Chances are you may need to modify the code above to fit your needs but I hope it serves as a stable launch point for you.

Cheers

==

Set the timeScale for pausing to something like .00001 instead of 0, and when pausing or resuming set the animation speeds to "1.0/Time.timeScale".

We use the following (clumsy, but workable) scheme. Most of our simulations run of a separate variable ourOwnDeltaTime, which is the same as Time.deltaTime when the game is running, but 0 when the game is paused. Things that should not pause runs off the proper deltaTime.

It is clumsy, because animations and particles have to be played and paused separately (because, of course, internally they still run of Time.deltaTime). It also requires a lot of discipline (you have to remember never to use the Time.deltaTime everywhere), and might not work well with 3rd party code.

A benefit is that game speed and interface animations can be controlled separately.

I could never understand why there is not a better built-in solution for pausing (in any game-engine I have worked with)...

You just have to control animation time manually - it works with regular or Unity animations. Get the actual delta time from realtimeSinceStartup or something else that is not affected by time scale and set appropriate time on your animation.

Here is my solution for animated tutorial in pause menu.

using UnityEngine;
using System.Collections;

public class TutorialAnimationControl : MonoBehaviour
{
    public AnimationClip[] animations;
    private int currentIndex = 0;
    bool isPlaying = false;
    bool isTutorial = false;
    float _startTime = 0F;
    float _progressTime = 0F;
    float _timeAtLastFrame = 0F;
    float _timeAtCurrentFrame = 0F;
    float deltaTime = 0F;
    AnimationState _currState;

    IEnumerator UpdateCoroutine ()
    {
        _timeAtLastFrame = Time.realtimeSinceStartup;
        while (isTutorial) {
            _timeAtCurrentFrame = Time.realtimeSinceStartup;
            deltaTime = _timeAtCurrentFrame - _timeAtLastFrame;
            _timeAtLastFrame = _timeAtCurrentFrame; 

            if (isPlaying) {
                _progressTime += deltaTime;
                _currState.normalizedTime = _progressTime / _currState.length; 
                animation.Sample ();

                if (_progressTime >= _currState.length) {
                    _currState.enabled = false;
                    isPlaying = false;
                    PlayNext();
                }
            }
            yield return new WaitForEndOfFrame();
        }
        yield return null;
    }

    void PlayAnimation (string suffix)
    {
        _progressTime = 0F;
        _currState = animation [suffix];
        _currState.weight = 1;
        _currState.blendMode = AnimationBlendMode.Blend;
        _currState.wrapMode = WrapMode.Once;
        _currState.normalizedTime = 0;
        _currState.enabled = true;
        isPlaying = true;
    }

    public void StartTutorial ()
    {
        isTutorial = true;
        PlayAnimation (animations [0].name);
        StartCoroutine (UpdateCoroutine ());
    }

    public void StopTutorial ()
    {
        isTutorial = false;
    }

    public void PlayNext ()
    {
        PlayAnimation (animations [(currentIndex++) % animations.Length].name);
    }
}