Для ваших требований самый простой способ - создать новый массив из ключей, отсортировать его, а затем использовать массив для ссылки на элементы из исходного словаря.
(Обратите внимание, что myComparison - это ваш собственный метод, который сравнивает два ключа).
NSMutableArray* tempArray = [NSMutableArray arrayWithArray:[myDict allKeys]];
[tempArray sortedArrayUsingSelector:@selector(myComparison:)];
for (Foo* f in tempArray)
{
Value* val = [myDict objectForKey:f];
}