What you want is in the simplest case a linear interpolation between 5 points in 3d. A direct color gradient between two colors {r1,g1,b1} and {r2,g2,b2} is, as you would walk onto the line in 3d which connects the points {r1,g1,b1} and {r2,g2,b2}.
When your gray-values are in the interval [0,1], then you would want to have the color {r1,g1,b1} if you have a gray-level 0 and {r2,g2,b2} if you have a gray-level 1. The question is how to calculate the colors in between:
think of the simple school vector analysis. c1 is the point {r1,g1,b1}, c2 is {r2,g2,b2}. Start at c1 and go in direction of the vector c2-c1:
outColor = c1 + gray*(c2-c1)
or equivalently
outColor = (1-gray)c1 + grayc2
Remenber, gray must lie in the interval [0,1]. Otherwise you have to rescale it. This is simple linear interpolation between two points which can of course be extended for as many colors as you want.
For five colors the approach is basically the same. Here for 5 randomly chosen colors:
{{0.273372, 0.112407, 0.0415183},
{0.79436, 0.696305, 0.167884},
{0.235083, 0.999163, 0.848291},
{0.295492, 0.780062, 0.246481},
{0.584883, 0.460118, 0.940826}}

Two important things you have to know:
If you want to have the color for a given gray-value, you first need to extract the two surrounding rgb-points. For instance if you want to have the color for gray=0.1 it would be the first and the second rgb-point.
You have to rescale your gray-value according to the number of colors which you use in your gradient. Look at the image, with 5 colors, you have 4 different two point interpolation intervals. When you want to make the above mentioned color formula work, you have to rescale your gray-value for each color-interval to [0,1].
Remark: This is of course not the solution for the implementation in C#, but your question suggested, that creating a color-image of the same size was not your problem. Calculating the color-values for each gray-value is the key for your colorization.