There are several things that you could try to do in this situation:
- make fedora faster
- get ubuntu to install
- find another distro
Currently your preference seems to be the latter; is that correct?
256 M ram is on the low side (partic for Gnome/KDE, which are the heavyweight GUIs), but should still be at least as fast as windows. During initial startup you may have one of several processes indexing the disk and that may be a factor in how slow it seems initially.
Puppy/dsl and similar are good suggestions. Also check out live CDs (DVDs), which allow you to try things out without installing.