Касательно того, с чем вкуснее есть холодец, то лично мне совсем не хочется употреблять расхожую фразу на предмет того, что мол вкусы у всех разные. Таковой ответ лично я считаю ответом из серии "ни о чём".
Рискну предположить, что есть старинное блюдо "холодец" или "студень" всё-таки надо с горчицей либо с хреном, потому как в пору создания сего кушанья, не было в обиходе российского и украинского и беларусского народов такой приправы как майонез или кетчуп, к примеру.
А вообще традиционно, думаю , что надо бы с хреном. Потому как пословице о том, что мол хрен редьки не слаще, тоже много времени, не один век. А посему, можно считать тёртый хрен старинной приправой и вполне в народе применяемой.
Мой вариант ответа такой, что традиционно холодец надо есть с хреном. Так заведено.
Ведь заведено же, чтобы суши кушали в соевым соусом и вассаби.