Я такой тест делал тремя запусками сравнительно короткого действия: заполнение BitmapData шумом, потом применение фильтров на нем. Замерял время, вычислял среднее и сравнивал с заранее заданными величинами.
К сожалению, такие тесты не берут в расчет текущую загрузку процессора, так что рекомендую, как минимум, показать пользователю результат теста с возможностью сразу изменить качество (если, конечно, не идет в конфликт с интерфейсом).
Еще вариант есть, если фреймрейт идет от таймера, а не от плеера, сделать код для фреймскипа и подсчета пропущенных кадров. Если кадров пропускается совсем много, понижать качество.
Наконец, про приоритет операции. На фоне проводить, конечно, "красивее", но вы уверены, что результаты не будут сбиты каким-то действием пользователя? Если все-таки решите делать фоновой операцией, посмотрите на очень приятную реализацию green thread'а
http://blog.generalrelativity.org/?p=29