How to smoothly change Color of a Brick?

You are able to use TweenService to smoothly transition between a whole range of properties (listed here). Color3s are one of these data types.

To create a tween, you first need to make a dictionary with the key of the property and the value of the goal colour:

local Goal = {
    Color = BrickColor.Random().Color --we want to get the Color3 part of the BrickColor
}

Then, we want to create the TweenInfo, which contains details about how the tween will work:

local Info = TweenInfo.new(3,Enum.EasingStyle.Linear) --tween will take 3 seconds and have a linear transition

After that, you can create the tween with that information and play it:

local Tween = game:GetService("TweenService"):Create(script.Parent, Info, Goal)
Tween:Play()

The part should then transition from the colour it is currently at to the new random goal colour. If you wanted to repeat this, you can set the RepeatCount parameter of TweenInfo.new() to math.huge (so it repeats indefinitely).