The pixel dimensions do not matter for display size when using Vector Graphics.
The beauty of vector graphics is they remain sharp at any size. It has to do with being defined with mathematical formulas rather than a pixel grid of fixed size.
So, to make a logo that will display nicely at any size, save it in a vector format. You are right to use a .Png. (this is only true with simple flat shapes and text, like you described yours as being).
A .PNG 24 with transparent background at 500 pixels should do the trick.
Use the "Save for Web" or new version its under "Export"
Make it, save it, blow it up so it fills your screen and check if the resolution is satisfactory, and if so then you're done. If not, if there is blur, jaggies or aliasing then go back into original .AI file, look it over for any defects, remove shadows, blur, edge effects or anything which doesn't look crisp, and save out as a .PNG again.
It wouldn't hurt to outline type and flatten everything before saving.
There are some tricks to make your logo visible as the video plays under it. All light or all dark will disappear when the underlying video is light or dark. I recommend contrasting thick outlines or bright mid range colors like yellow or orange.
The answer above does raise important issues of proportion, making sure your logo stays the right shape on different screen sizes. I believe after effects can apply graphics that will not distort any more than the video itself, but it's something you'll have to look into.
I've seen some questions/answers on here discussing making many versions of a logo for different screen ratios and pixel density.