Air Canada gives 500 mile minimum to all members. They are part of Star Alliance, and you can reach Elite status (Star Alliance Gold) with only 35K miles. Elite status also gives you FREE access to all Maple Leaf Lounges, Red Carpet Clubs, US Airways Lounge, etc.

I should also add that you get the 500 mile minimum even when flying on UA or US metal as long as the miles are credited to Aeroplan, so great for Mileage Runs with many short segments.