We know that gradient is a vector which denotes the direction of maximum rate of change of the function and it's perpendicular to the graph of the function.
So is it necessary for all kind of surfaces denoted by three dimensional functions to change at their normal direction mostly?
Let's be clear about what we mean by the graph of a function. I'm going to get all pedantic on you, not because you don't know what you're doing (I can't tell whether you do or not), but because when I was a student of multivariable calculus, statements like the ones you just made were barriers to my ability to understand the topic. I would like to try to remove those barriers for anyone reading this who is in the position I was in then.
When we take the graph of a function of one variable, $f(x),$ we get a graph in two dimensions: one dimension is $x$ and the other is the value of $f(x),$ often written $y = f(x).$ The figure below is an example of a graph of the function $f(x) = x^2 - 3x - 4.$
In order to graph a function of two variables, $f(x,y),$ we need three dimensions. We might write $z = f(x,y)$ and "plot" this as a surface in the three-dimensional space with coordinates $x,$ $y,$ and $z.$
In order to "graph" a function $f(x,y,z),$ which has three variables, we need four dimensions. Very few of us can visualize four dimensions clearly enough for such a "graph" to be of any use.
But the gradient of a function $f(x,y)$ is only two-dimensional, contained entirely in the $x,y$ plane. In general it is not perpendicular to the surface that constitutes the graph of the function. The gradient of $f(x,y,z)$ also has too few dimensions in order to be perpendicular to the "graph" of that function (it lives only in $x,y,z$ space but would need to have a component in the fourth dimension as well).
In this sense, the gradient of a function cannot be perpendicular to the function's graph, because the only surfaces to which the gradient could be perpendicular are not differentiable at that point.
What the gradient is perpendicular to is something called a level set. In two dimensions this would be the solution to an equation such as $f(x,y) = k,$ and it might be called a level curve. In three dimensions it would be the solution to an equation such as $f(x,y,z) = k$ and might be called a level surface.
A level set is a graph related to a function, but it is not "the graph of the function" by any stretch of the imagination. After all, the surfaces described by $f(x,y,z) = 0,$ by $f(x,y,z) = 1,$ and by $f(x,y,z) = 273$ are all level surfaces of $f(x,y,z),$ and they're all different. None of them deserves to be called "the" graph of $f(x,y,z).$
The fact that the gradient is perpendicular to the level set is just another way of saying that the directions in which the value of the function is not changing at all (in the sense that the value of $x^2$ is "not changing at all" at $x = 0$) are all perpendicular to the direction in which the function changes the fastest.
It may be possible to come up with an example of a function that violates this rule at some point in its input space, but then it will not be differentiable there and will not have a gradient at that point.