After graduating from Greenwood High School, Miller became a student at Memphis State University in 1973, attending with a band scholarship. He played euphonium, but, during his two years at the university, Miller met pianists Donald Brown and James Williams, who introduced him to the music of well-known players such as Wynton Kelly, Bud Powell, and McCoy Tyner. Still at Memphis State, Miller attended a jazz workshop, where one of the tutors was his future bandleader, Woody Shaw, who stated that they would meet again in two years. They did meet again two years later, and Shaw remembered the young pianist. After leaving university in 1975, Miller took lessons privately in Boston with Madame Margaret Chaloff, who had taught many of the pianists that Miller admired. He later commented that, "I should have stayed with her longer, [...] but at that time I was so restless, constantly on the move." Miller played with saxophonists Ricky Ford and Bill Pierce in Boston. That winter, Miller was invited to Los Angeles by a school friend and decided to go, to escape the northern cold. He stayed on the West Coast for a year, playing locally in clubs and a church.