using System;
using System.Security.Cryptography;
using System.Text;

namespace LANDesk.Licensing.WebServices.Business
{
    public class CryptoRandomString
    {
        public static string GetCryptoRandomBase64String(int length)
        {
            var buffer = new byte[length];
            using (var rngCryptoServiceProvider = new RNGCryptoServiceProvider())
            {
                rngCryptoServiceProvider.GetNonZeroBytes(buffer);
            }
            return Convert.ToBase64String(buffer);
        }
        
        public static string GetCryptoRandomBaseNString(int length, byte baseN)
        {
            if (length < 1)
                throw new ArgumentException("The string length must be greater than 0!");
            if (baseN < 2)
                throw new ArgumentException("The base must be 2 or greater!");

            var buffer = new byte[length];
            var builder = new StringBuilder();

            using (var rngCryptoServiceProvider = new RNGCryptoServiceProvider())
            {
                rngCryptoServiceProvider.GetBytes(buffer);
                foreach (var b in buffer)
                {
                    var tmpbuff = new byte[] { b };
                    int max = (baseN * (256 / baseN)) - 1; // minus 1 because we start at 0
                    while (tmpbuff[0] > max)
                    {
                        rngCryptoServiceProvider.GetBytes(tmpbuff);
                    }
                    var singleChar = ByteToBaseNChar(tmpbuff[0], baseN, 32); // Start at ascii 32 (space)
                    builder.Append(singleChar);
                }
            }
            return builder.ToString();
        }

        public static string GetCryptoRandomBase95String(int length)
        {
            return GetCryptoRandomBaseNString(length, 95);
        }

        public static char ByteToBaseNChar(byte b, int baseN, int asciiOffset)
        {
            return (char)(b % baseN + asciiOffset);
        }
    }
}

And here are a few tests for it. If you can think of a additional tests, please let me know.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text.RegularExpressions;
using LANDesk.Licensing.WebServices.Business;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace LANDesk.Licensing.WebServices.Tests.Business
{
    [TestClass]
    public class CryptoRandomStringTests
    {
        [TestMethod]
        public void TestTestThatCorrectCharacterCountIsReturned()
        {
            const int length = 100;
            var randomString = CryptoRandomString.GetCryptoRandomBase95String(length);
            Assert.AreEqual(length, randomString.Length);
        }

        [TestMethod]
        public void TestAllCharactersAreUsed()
        {
            const int length = 1000000;
            var randomString = CryptoRandomString.GetCryptoRandomBase95String(length);
            for (int i = 32; i < 126; i++)
            {
                char c = (char)i;
                Assert.IsTrue(randomString.Contains(c.ToString()));
            }
        }

        [TestMethod]
        public void TestPerformanceTenMillionCharacters()
        {
            Stopwatch watch = new Stopwatch();
            watch.Start();
            const int length = 1000000;
            var randomString = CryptoRandomString.GetCryptoRandomBase95String(length);
            watch.Stop();
            Assert.IsTrue(watch.ElapsedMilliseconds < 1000);
        } // Elapsed Milliseconds 320 (it fluxuated a few milliseconds each run) 

        [TestMethod]
        public void TestPerformanceLoop()
        {
            Stopwatch watch = new Stopwatch();
            const int length = 16;
            watch.Start();
            for (int i = 0; i < 100000; i++)
            {
                var randomString = CryptoRandomString.GetCryptoRandomBase95String(length);
            }
            watch.Stop();
            Assert.IsTrue(watch.ElapsedMilliseconds < 1000);
        }

        [TestMethod]
        public void TestDistributionInTenMillionCharacters()
        {
            const int length = 1000000;
            const int distibution = length / 95;
            int[] margins = new int[9500];
            for (int j = 0; j < 100; j++)
            {
                var randomString = CryptoRandomString.GetCryptoRandomBase95String(length);
                for (int i = 32; i < 127; i++)
                {
                    //int count = randomString.Count(c => c == i);
                    int count = CountInstancesOfChar(randomString, (char)i);
                    margins[(j * 95) + i - 32] = count;
                }
            }
            Assert.IsTrue(Math.Abs(margins.Average() - distibution) < .5);
        }

        private int CountInstancesOfChar(string str, char c)
        {
            int count = 0;
            char[] strArray = str.ToCharArray();
            int length = str.Length;
            for (int n = length - 1; n >= 0; n--)
            {
                if (strArray[n] == c)
                    count++;
            }
            return count;
        }
    }
}