Faits : A. Par avis publié le 26 décembre 2014 dans le Bulletin officiel (BO) du canton du Valais, l'administration de la Commune de Randogne a mis à l'enquête un projet d'aménagement de l'avenue de la Gare. Le projet porte, pour l'essentiel, sur le réaménagement de l'ensemble de l'espace routier de cette avenue, sur l'installation d'aménagements urbains décoratifs ainsi que sur la mise en place d'un espace de rencontre. Ce projet a notamment suscité l'opposition de A._, propriétaire d'un immeuble sis à l'avenue de la Gare xxx. Par décision du 24 février 2016, le Conseil d'Etat du canton du Valais a, d'une part, approuvé les plans et les documents techniques relatifs à ce projet; d'autre part, reconnaissant la qualité pour agir de A._, il a rejeté son opposition. A._ a recouru contre cette décision à la Cour de droit public du Tribunal cantonal du canton du Valais. Par arrêt du 17 juin 2016, la cour cantonale a déclaré le recours irrecevable. L'instance précédente a en substance jugé que le recours était insuffisamment motivé au regard des exigences du droit cantonal et que le recourant n'avait pas démontré avoir un intérêt pratique à l'annulation du projet. B. Agissant par la voie du recours en matière de droit public, A._ demande principalement au Tribunal fédéral d'annuler le projet de réaménagement litigieux; subsidiairement, il conclut au renvoi de la cause à l'instance précédente pour nouvelle décision dans le sens des considérants. Il sollicite également l'octroi de l'effet suspensif, qui a été refusé par ordonnance du 26 août 2016. Le Tribunal cantonal a renoncé à se déterminer. La Commune de Randogne demande au Tribunal fédéral, à la forme, de déclarer le recours irrecevable et, sur le fond, de le rejeter.