Find the longest connect cells region per color
Looks fine overall, but there are a few oddities here and there, and there are some opportunities for significant performance improvements:


Since you're going to visit every node in the given int[,] graph you might as well use a bool[,] instead of a Dictionary&lt;int, HashSet&lt;Tuple&lt;int, int&gt;&gt;&gt;. I see no reason to group visited nodes per color, because you're already keeping track of the largest group separately. For me, this made things about 6x faster.
Using an 'old-style' tuple as return type isn't very descriptive. Consider using value-tuples instead: public static (int color, int count) FindLongestConnectedColor().
In GetConnectedRegionLength, I'd combine directionRow and directionColumn into a single array of (int x, int y) tuples. Not a list - it's not going to be resized. This also provides a small performance increase. Also consider storing it in a static field, so you only need to initialize the array once, for yet another performance increase.
q1 and q2 are rather undescriptive names - openNodes would be better. It's also unclear why there are two queues instead of one (you mentioned the reason in your post, but it's not documented in the code). About that reason - Queue&lt;T&gt; is generic, so a Queue&lt;Tuple&lt;int, int&gt;&gt; or Queue&lt;(int, int)&gt; is not going to involve boxing. Yes, you'll need to create tuple objects, but you no longer need to call Enqueue and Dequeue twice. Performance should be more or less the same. When in doubt, measure!
connectedCellsCount can be initialized to 1 directly.
while (q1.Count &gt; 0) is faster than while (q1.Any()).
a is rather uncommon as a counter variable name - I'd stick to i.
Personally I'm not a fan of putting single if-body statements on the same line: if (...) continue;. It makes these 'early-outs' more difficult to spot when scanning code.
The various if/continue statements can be combined into a single if.


As for breadth-first versus depth-first, I guess I don't really see the point here: the only difference is the order in which you visit nodes, but you still have to visit all of them. Either way, instead of recursion you can also combine iterative code with a stack data-structure. Similar to your current solution, just with a stack instead of a queue.