Tiles and slices provide different frame partitioning options. While they can both be used for video coding parallelization, tiles offer better scalability to the number of available processors, especially as far as video quality is concerned, e.g., in the HEVC case. On the other hand, slices can be useful in video transmission. Since slices can be defined as a series of consecutive (raster order) tiles, properly balancing them can lead to viable trade-offs between parallelization and transmission requirements. In this paper we study the combined problem of tile and slice partitioning with the goals of maximizing the achievable parallelism speedup, while minimizing size difference among slices. These goals might conflict with each other, while producing multiple Pareto frontier solutions can introduce additional time overhead. For these reasons, we map the two-function optimization problem to a single one, using constant weighting and develop algorithms that perform tile resizing and slice definition so as to optimize the composite target function. Experiments with common class A and class B test sequences and the reference HEVC encoder (HM), reveal that compared to static uniform tile partitioning and to literature alternatives that resize tiles in order to increase parallelization speedup, the proposed algorithm achieves considerable gains in slice balancing, while also improving speedup over the static approach. Furthermore, these performance merits come with negligible overhead to the encoding process.