Would a better heat sink be tall or wide?
If the airflow is vertical (e.g., convection), you want a wider heatsink that can contact a larger volume of air. Increasing the height would simply put more heat into air that you've already heated.

Similarly, if the airflow is horizontal, you want a taller heatsink.

In either case, you want to make sure that any fins on the heatsink are oriented parallel to the airflow.

Of course, all of this must take into account the constraints of the physical packaging of the product. In general, as long as you increase the total surface area of the heatsink, you'll come out ahead.