Edit 2:

You should add more descriptive names. I don't know what bi, bc, the nl in nlGaps, etc. stand for. Short names are okay for lambda expressions and loop variables, but even then you should stick to x, y, i, j, or a letter that relates to the object. I think it would make more sense to use r for a rectangle than b.

You can have a boolean as a parameter and select X or Y and Width or Height based on that parameter. You can declare the method like this:

private List<Rectangle[]> GroupRectangles(Rectangle[] rectangles, bool horizontally, out int averageGap)

You can use the code from the horizontal method and modify the property calls to use the boolean. For example, you would replace rectangle.X with horizontally ? rectangle.X : rectangle.Y and rectangle.Width with horizontally ? rectangle.Width : rectangle.Height.

It can then be used in your previous methods:

private List<Rectangle[]> GroupRectanglesHorizontally(Rectangle[] rectangles, out int averageGap)
{
    return GroupRectangles(rectangles, true, out averageGap);
}


private List<Rectangle[]> GroupRectanglesVertically(Rectangle[] rectangles, out int averageGap)
{
    return GroupRectangles(rectangles, false, out averageGap);
}

Alternatively, you could have functions as parameters for selecting the properties, like using a lambda expression in OrderBy().

You can have a boolean as a parameter and select X or Y and Width or Height based on that parameter. You can declare the method like this:

private List<Rectangle[]> GroupRectangles(Rectangle[] rectangles, bool horizontally, out int averageGap)

You can use the code from the horizontal method and modify the property calls to use the boolean. For example, you would replace rectangle.X with horizontally ? rectangle.X : rectangle.Y and rectangle.Width with horizontally ? rectangle.Width : rectangle.Height.

It can then be used in your previous methods:

private List<Rectangle[]> GroupRectanglesHorizontally(Rectangle[] rectangles, out int averageGap)
{
    return GroupRectangles(rectangles, true, out averageGap);
}


private List<Rectangle[]> GroupRectanglesVertically(Rectangle[] rectangles, out int averageGap)
{
    return GroupRectangles(rectangles, false, out averageGap);
}

Alternatively, you could have functions as parameters for selecting the properties, like using a lambda expression in OrderBy().

Edit: as for the first method itself:

In the following line of code:

Rectangle[] baSimiliarHeight = rectangles.Where(b => Math.Abs(b.Y - rectangles[bi].Y) <= nTolerance
                                                        && b.X > rectangles[bi].X)
                                                .ToArray();

it won't get rectangles that are at the exact same X position. But that won't matter if it's guaranteed that none of the rectangles overlap. Then there's this code right after:

if (baSimiliarHeight.Length <= 1)
{
    rectangleGroups.Add(new Rectangle[] { rectangles[bi] });
    continue;
}

Because rectangles with the same X position weren't matched before, baSimiliarHeight won't contain rectangles[bi], so if it has a length of 1, that 1 element will be a different rectangle, but only the original rectangle will get added as a group.

In the inner for loop, the body of the last else only adds the initial rectangle, but doesn't do anything about the previously added nGaps, so it's possible for the loop to add a bunch of nGaps but only add the initial rectangle.

If you get a list of the rectangles ordered by their X position right away and loop through that instead of the original list, you can take some shortcuts in the body of the for loop.