A (k, m)-Furstenberg set S subset of F-q(n) over a finite field is a set that has at least m points in common with a k-flat in every direction. The question of determining the smallest size of such sets is a natural generalization of the finite field Kakeya problem. The only previously known bound for these sets is due to Ellenberg-Erman  and requires sophisticated machinery from algebraic geometry. In this work we give new, completely elementary and simple proofs that significantly improve the known bounds. Our main result relies on an equivalent formulation of the problem using the notion of min-entropy, which could be of independent interest.