Верно: палаццо Веккьо.

По общему правилу склоняемость или несклоняемость фамилий, пишущихся с буквой я на конце, зависит только от места ударения и происхождения фамилии. Не склоняются фамилии французского происхождения с ударением на конце (Золя, Труайя). Все прочие фамилии на я склоняются по первому склонению (Головня, Гойя, Данелия). См. подробнее наш справчный материал Как склонять фамилии (трудные случаи). Но, к сожалению, к фамилиям типа Юрця неприменимо понятие «правильно» в орфографическом смысле этого слова, поскольку в самой фамилии есть орфографический казус (буква я после ц), который мешает принятию однозначного решения. В таких случаях следует руководствоваться существующей практикой употребления фамилии (обычно известной ее носителям).

Предпочтительно: кубики, окрашенные в синий, красный, зелёный цвета.