Is it safe to Unprotect everything? What are the implications?

The reason is to prevent users to mess with it. Unprotecting something is not necessarily dangerous, but unprotecting everything definitely is. Performance is probably not the issue. The real danger is that you replace a very important feature of a built-in symbol by chance. Since built-in symbols often have the ReadProtected attribute, you cannot check beforehand whether you are going to overwrite anything important.

Regarding the appearance of held expressions: One can do this

Unprotect[Hold];
Format[Hold[a___]] := Held[a];
Protect[Hold];

at the cost of the puzzling results

a = Hold[1 + 1]
a // FullForm

(* Held[2] *)
(* Hold[1 + 1] *)

Internally, the expression should be treated by Mathematica as usual; only the appearance was changed in a counterintuitive way. This particular issue can be fixed by giving the HoldAll attribute to Held:

SetAttributes[Held,HoldAll]
a
(* Held[1+1] *)

But still, messing with internals is a very, very bad idea.

Addendum: Mathematica also provides the attribute Locked which prevents changing the Attibutes of a symbol. If that symbol has also the attribute Protected then it cannot be messed with any more. That seems to be the way how developers are meant to protect their users from themselves. However, one cannot rely on the combination Protected and Locked being used consistently for all "important" symbols.

There is a typesetting step after formatting, and MakeBoxes definitions do not require unprotecting Hold, you will just add more DonwValues for MakeBoxes.

MakeBoxes[Hold[a___], fmt_] := With[
    {foo = MakeBoxes[Panel[Column[{a}]], fmt]}
  , InterpretationBox[
        RowBox[{"Hold", "[", foo, "]"}]
      , Hold[a]
    ]
]

Hold[1 + 1, 2 + 2, 4 + 4]

It is always crucial to not let any evaluation leak during typesetting. Here, the content from Hold is passed directly to another MakeBoxes which holds its arguments.