I did some research, and it appears this won't be answered with a simple straight answer. This page has all the release dates for Blu-ray disc up-to-date, and this page (and this forum thread too) has all the HD DVD release dates up until the format was discontinued.
The first occurrence of anime in either format is The Ultimate Matrix Collection, released on HD DVD on May 22nd, 2007. This makes it to the list because The Animatrix is included in the collection. If this means the question is answered for you, then no need to read on. If you wanna try to find the first anime title released on its own, read on.
The second occurrence is Final Fantasy: The Spirits Within, released on Blu-ray disc on August 7th, 2007. It does have a page on MAL, but it may not be regarded as anime by everyone given that it is described on most places (including Wikipedia) as an "American computer-animated science fiction film".
After that come two titles, one in each format, released with very little time difference between them.
First, comes a 1987 movie, Royal Space Force: Wings of Honneamise, released on HD DVD on September 11th, 2007. It is also known by its Japanese title, Ouritsu Uchuugun: Honneamise no Tsubasa.
Just 14 days afterwards, comes Tekkon Kinkreet, released on Blu-ray disc on September 25th, 2007. And here's its MAL page.