Как работает getline()?

Здесь же почему-то getline() каким-то образом "перебивает" cin сверху, и считывает количество строк как еще одну строку, как я понял из теста проги(но это не точно)

Нет, все проще. После считывания количества строк в буфере остается символ перевода строки. Вам просто надо сбросить буфер после считывания N - например, так:

cin.ignore(std::numeric_limits<size_t>::max(), '\n');

(это означает - считать и игнорировать все, пока не встретим '\n').

Еще - я бы переписал ваш оператор как

bool operator()(char expr) {
    return strchr("aoiuye",expr) != nullptr;
}

Остальное не смотрел...

После этого предложения

cin >> N;

в буфере потока ввода сохранился символ новой строки '\n'. Поэтому первое обращение к буферу ввода с помощью функцииgetline` приводит к тому, что считывается пустая строка.

Следует удалить этот символ новой строки из буфера перед использованием getline Делается это следующим образом

#include <iostream>
#include <string>
#include <algorithm> 
#include <limits>
^^^^^^^^^^^^^^^^^
#include <conio.h>   
using namespace std;
class count_predicate {
public:
    bool operator()(const char& expr) {
        if (
            expr == 'a' || expr == 'o' || expr == 'i'
            || expr == 'u' || expr == 'y' || expr == 'e'
           ) return true;
        return false;
    }
};
int main()
{
    int N; // Нужное количество строк
    cin >> N;
    string strs[N];
    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   // ...

Предикат может быть записан проще

#include <cstring>
//...
struct count_predicate 
{
    bool operator()( const char &c ) const
    {
        const char *vowels = "aeiouy";
        return std::strchr( vowels, c );
    }
};